Introduction

NOTE: This is an R Markdown Notebook. When you execute code within the notebook, the results appear beneath the code.

In previous practice/session, you learned about how to use local spatial statistics for exploratory spatial data analysis.

For this practice you will need the following:

The shape file includes spatial information for Traffic Analysis Zones (TAZ) in the Hamilton Census Metropolitan Area (as polygons).

Learning objectives

In this practice, you will:

  1. Revisit the notion of autocorrelation as a model diagnostic.
  2. Remedial action.
  3. Flexible functional forms and models with spatially-varying coefficients. 3.1 Trend surface analysis. 3.2 The expansion method. 3.3 Geographically weighted regression (GWR).
  4. Spatial error model (SEM).

Suggested reading

O’Sullivan D and Unwin D (2010) Geographic Information Analysis, 2nd Edition, Chapter 7. John Wiley & Sons: New Jersey.

Preliminaries

As usual, it is good practice to clear the working space to make sure that you do not have extraneous items there when you begin your work. The command in R to clear the workspace is rm (for “remove”), followed by a list of items to be removed. To clear the workspace from all objects, do the following:

rm(list = ls())

Note that ls() lists all objects currently on the worspace.

Load the libraries you will use in this activity:

library(tidyverse)
-- Attaching packages --------------------------------------------------------------------- tidyverse 1.2.1 --
v ggplot2 3.0.0     v purrr   0.2.5
v tibble  1.4.2     v dplyr   0.7.5
v tidyr   0.8.1     v stringr 1.3.1
v readr   1.1.1     v forcats 0.3.0
package 㤼㸱ggplot2㤼㸲 was built under R version 3.4.4package 㤼㸱tidyr㤼㸲 was built under R version 3.4.4package 㤼㸱purrr㤼㸲 was built under R version 3.4.4package 㤼㸱dplyr㤼㸲 was built under R version 3.4.4package 㤼㸱stringr㤼㸲 was built under R version 3.4.4package 㤼㸱forcats㤼㸲 was built under R version 3.4.4-- Conflicts ------------------------------------------------------------------------ tidyverse_conflicts() --
x dplyr::filter() masks stats::filter()
x dplyr::lag()    masks stats::lag()
library(rgdal)
package 㤼㸱rgdal㤼㸲 was built under R version 3.4.4Loading required package: sp
package 㤼㸱sp㤼㸲 was built under R version 3.4.4rgdal: version: 1.3-2, (SVN revision 755)
 Geospatial Data Abstraction Library extensions to R successfully loaded
 Loaded GDAL runtime: GDAL 2.2.3, released 2017/11/20
 Path to GDAL shared files: C:/Users/Antonio/Documents/R/win-library/3.4/rgdal/gdal
 GDAL binary built with GEOS: TRUE 
 Loaded PROJ.4 runtime: Rel. 4.9.3, 15 August 2016, [PJ_VERSION: 493]
 Path to PROJ.4 shared files: C:/Users/Antonio/Documents/R/win-library/3.4/rgdal/proj
 Linking to sp version: 1.3-1 
library(broom)
package 㤼㸱broom㤼㸲 was built under R version 3.4.4
library(spdep)
package 㤼㸱spdep㤼㸲 was built under R version 3.4.4Loading required package: Matrix

Attaching package: 㤼㸱Matrix㤼㸲

The following object is masked from 㤼㸱package:tidyr㤼㸲:

    expand

Loading required package: spData
package 㤼㸱spData㤼㸲 was built under R version 3.4.4
library(reshape2)

Attaching package: 㤼㸱reshape2㤼㸲

The following object is masked from 㤼㸱package:tidyr㤼㸲:

    smiths
library(plotly)
package 㤼㸱plotly㤼㸲 was built under R version 3.4.4
Attaching package: 㤼㸱plotly㤼㸲

The following object is masked from 㤼㸱package:ggplot2㤼㸲:

    last_plot

The following object is masked from 㤼㸱package:stats㤼㸲:

    filter

The following object is masked from 㤼㸱package:graphics㤼㸲:

    layout
library(knitr)
package 㤼㸱knitr㤼㸲 was built under R version 3.4.4
library(kableExtra)
package 㤼㸱kableExtra㤼㸲 was built under R version 3.4.4
library(spgwr)
NOTE: This package does not constitute approval of GWR
as a method of spatial analysis; see example(gwr)

Begin by loading the shape file:

Hamilton_TAZ <- readOGR(".", layer = "Hamilton CMA tts06")
OGR data source with driver: ESRI Shapefile 
Source: "C:\Antonio\Courses\GEOG 4GA3 - Applied Spatial Analysis\Spatial-Statistics-Course\15. Area Data VI\01. Readings and Practice", layer: "Hamilton CMA tts06"
with 297 features
It has 12 fields
Integer64 fields read as strings:  ID NUM GTA06 GTA01 AREA_M AREA_H 

The shape file includes the geometry of the zones only.

To use the plotting functions of ggplot2, the SpatialPolygonDataFrame needs to be “tidied” by means of the tidy function of the broom package:

Hamilton_TAZ.t <- tidy(Hamilton_TAZ, region = "GTA06")
Hamilton_TAZ.t <- dplyr::rename(Hamilton_TAZ.t, GTA06 = id)

Tidying the spatial dataframe strips it from the non-spatial information, but we can add all the data by means of the left_join function:

Hamilton_TAZ.t <- left_join(Hamilton_TAZ.t, Hamilton_TAZ@data, by = "GTA06")
Column `GTA06` joining character vector and factor, coercing into character vector

Now the tidy dataframe Hamilton_DA.t contains the spatial information and the data.

You can quickly verify the contents of the dataframe by means of summary:

summary(Hamilton_TAZ.t)
      long             lat            order          hole         piece         group      
 Min.   :-80.25   Min.   :43.05   Min.   :    1   Mode :logical   1:11772   4050.1 :  266  
 1st Qu.:-79.90   1st Qu.:43.21   1st Qu.: 2949   FALSE:11784     2:   16   4052.1 :  239  
 Median :-79.85   Median :43.25   Median : 5896   TRUE :8         3:    4   6007.1 :  239  
 Mean   :-79.83   Mean   :43.26   Mean   : 5896                             5211.1 :  226  
 3rd Qu.:-79.79   3rd Qu.:43.29   3rd Qu.: 8844                             5191.1 :  191  
 Max.   :-79.51   Max.   :43.48   Max.   :11792                             6018.1 :  148  
                                                                            (Other):10483  
    GTA06                 ID             AREA              NUM              PD            REGION      
 Length:11792       2299   :  266   Min.   : 0.1083   0      :10560   Min.   : 0.00   Min.   : 5.000  
 Class :character   2301   :  239   1st Qu.: 1.0316   11007  :  239   1st Qu.: 0.00   1st Qu.: 6.000  
 Mode  :character   583    :  239   Median : 1.7958   11018  :  148   Median : 0.00   Median : 6.000  
                    2842   :  226   Mean   : 6.1606   11008  :  127   Mean   : 8.68   Mean   : 6.305  
                    2823   :  191   3rd Qu.: 4.1323   11006  :  107   3rd Qu.: 0.00   3rd Qu.: 6.000  
                    594    :  148   Max.   :90.7720   11012  :  107   Max.   :40.00   Max.   :11.000  
                    (Other):10483                     (Other):  504                                   
     GTA01      AREA_M    AREA_H      UTMX_CENT   UTMY_CENT DISTRICT_N
 0      :9104   0:11792   0:11792   Min.   :0   Min.   :0   11:1232   
 2050   : 266                       1st Qu.:0   1st Qu.:0   5 :2559   
 2052   : 239                       Median :0   Median :0   6 :8001   
 2556   : 110                       Mean   :0   Mean   :0             
 2091   :  96                       3rd Qu.:0   3rd Qu.:0             
 2098   :  63                       Max.   :0   Max.   :0             
 (Other):1914                                                         

Residual spatial autocorrelation revisited

Previously you learned about the use of Moran’s I coefficient as a diagnostic in regression analysis.

Residual spatial autocorrelation is a symptom of a model that has not been properly specified. There are two reasons for this that are of interest:

  1. The functional form is incorrect.
  2. The model failed to include relevant variables.

Lets explore these in turn.

Incorrect functional form

To illustrate this, we will simulate a spatial process as follows: \[ z = f(x,y) = exp(\beta_0)exp(\beta_1x)exp(\beta_2y) + \epsilon_i \]

Clearly, this is a non-linear spatial process.

The simulation is as follows, with a random term with a mean of zero and standard deviation of 1. The random terms are independent by design:

set.seed(10)
b0 = 1
b1 = 2
b2 = 4
xy_coords <- coordinates(Hamilton_TAZ)
Hamilton_TAZ@data <- mutate(Hamilton_TAZ@data,
                            x = xy_coords[,1] - min(xy_coords[,1]),
                            y = xy_coords[,2] - min(xy_coords[,2]),
                            z = exp(b0) * exp(b1 * x) * exp(b2 * y) +
                              rnorm(n = 297, mean = 0, sd = 1))
package 㤼㸱bindrcpp㤼㸲 was built under R version 3.4.4
summary(Hamilton_TAZ@data[,13:15])
       x                y                z         
 Min.   :0.0000   Min.   :0.0000   Min.   : 3.761  
 1st Qu.:0.2810   1st Qu.:0.1226   1st Qu.: 8.222  
 Median :0.3316   Median :0.1550   Median : 9.958  
 Mean   :0.3348   Mean   :0.1681   Mean   :10.885  
 3rd Qu.:0.3850   3rd Qu.:0.1976   3rd Qu.:12.534  
 Max.   :0.6518   Max.   :0.3683   Max.   :22.358  

Suppose that we estimate the model as a linear regression that does not correctly capture the non-linearity. The model would be as follows:

model1 <- lm(formula = z ~ x + y, data = Hamilton_TAZ@data) 
summary(model1)

Call:
lm(formula = z ~ x + y, data = Hamilton_TAZ@data)

Residuals:
     Min       1Q   Median       3Q      Max 
-2.73799 -0.85271  0.01062  0.77256  3.07456 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  -4.2480     0.3169  -13.41   <2e-16 ***
x            21.9485     0.6798   32.29   <2e-16 ***
y            46.2989     1.0019   46.21   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1.196 on 294 degrees of freedom
Multiple R-squared:  0.9014,    Adjusted R-squared:  0.9007 
F-statistic:  1343 on 2 and 294 DF,  p-value: < 2.2e-16

At first glance, the model gives the impression of a very good fit: all coefficients are significant, and the coefficient of multiple determination \(R^2\) is very high.

At this point, it is important to examine the residuals to verify that they are independent. Lets add the residuals of this model to your dataframes:

Hamilton_TAZ@data$model1.e <- model1$residuals
Hamilton_TAZ.t <- left_join(Hamilton_TAZ.t, 
                           data.frame(GTA06 = Hamilton_TAZ$GTA06, model1$residuals))
Joining, by = "GTA06"
Column `GTA06` joining character vector and factor, coercing into character vector
Hamilton_TAZ.t <- rename(Hamilton_TAZ.t, model1.e = model1.residuals)

A map of the residuals can help examine their spatial pattern:

map.e1 <- ggplot(data = Hamilton_TAZ.t, aes(x = long, y = lat, group = group,
                                  fill = model1.e)) +
  geom_polygon(color = "white") +
  coord_equal() +
  scale_fill_distiller(palette = "RdBu")
ggplotly(map.e1)

To test the residuals for spatial autocorrelation we first create a set of spatial weights:

Hamilton_TAZ.w <- nb2listw(poly2nb(Hamilton_TAZ))

With this, we can now calculate Moran’s I:

moran.test(Hamilton_TAZ$model1.e, Hamilton_TAZ.w)

    Moran I test under randomisation

data:  Hamilton_TAZ$model1.e  
weights: Hamilton_TAZ.w    

Moran I statistic standard deviate = 9.3976, p-value < 2.2e-16
alternative hypothesis: greater
sample estimates:
Moran I statistic       Expectation          Variance 
      0.317160954      -0.003378378       0.001163393 

The test does not allow us to reject the null hypothesis of spatial independence. Thus, despite the apparent goodness of fit of the model, there is reason to believe something is missing.

Lets now use a variable transformation to approximate the underlying non-linear process:

model2 <- lm(formula = log(z) ~ x + y, data = Hamilton_TAZ@data)
summary(model2)

Call:
lm(formula = log(z) ~ x + y, data = Hamilton_TAZ@data)

Residuals:
     Min       1Q   Median       3Q      Max 
-0.31731 -0.06268  0.00447  0.07483  0.28175 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  0.96804    0.02721   35.58   <2e-16 ***
x            2.07419    0.05837   35.53   <2e-16 ***
y            3.97461    0.08603   46.20   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1027 on 294 degrees of freedom
Multiple R-squared:  0.9066,    Adjusted R-squared:  0.9059 
F-statistic:  1426 on 2 and 294 DF,  p-value: < 2.2e-16

This model does not necessarily have a better goodness of fit. However, when we test for spatial autocorrelation:

Hamilton_TAZ@data$model2.e <- model2$residuals
moran.test(Hamilton_TAZ$model2.e, Hamilton_TAZ.w)

    Moran I test under randomisation

data:  Hamilton_TAZ$model2.e  
weights: Hamilton_TAZ.w    

Moran I statistic standard deviate = 0.58286, p-value = 0.28
alternative hypothesis: greater
sample estimates:
Moran I statistic       Expectation          Variance 
      0.016485452      -0.003378378       0.001161455 

Once that the correct functional form has been specified, the model is better at capturing the underlying process (check how the coefficients approximate to a high degree the true coefficients of the model). In addition, we can conclude that the residuals are independent, and therefore are now also spatially random: meaning the there is nothing left of the process but white noise.

Omitted variables

Using the same example, suppose now that the function form is correctly specified, but a relevant variable is missing:

model3 <- lm(formula = log(z) ~ x, data = Hamilton_TAZ@data)
summary(model3)

Call:
lm(formula = log(z) ~ x, data = Hamilton_TAZ@data)

Residuals:
     Min       1Q   Median       3Q      Max 
-0.70236 -0.17279 -0.04807  0.13260  0.83999 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  1.81774    0.05753   31.60   <2e-16 ***
x            1.53226    0.16406    9.34   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.2947 on 295 degrees of freedom
Multiple R-squared:  0.2282,    Adjusted R-squared:  0.2256 
F-statistic: 87.23 on 1 and 295 DF,  p-value: < 2.2e-16

As before, lets append the residuals to the dataframes:

Hamilton_TAZ@data$model3.e <- model3$residuals
Hamilton_TAZ.t <- left_join(Hamilton_TAZ.t, 
                           data.frame(GTA06 = Hamilton_TAZ$GTA06, model3$residuals))
Joining, by = "GTA06"
Column `GTA06` joining character vector and factor, coercing into character vector
Hamilton_TAZ.t <- rename(Hamilton_TAZ.t, model3.e = model3.residuals)

A map of the residuals can help examine their spatial pattern:

map.e3 <- ggplot(data = Hamilton_TAZ.t, aes(x = long, y = lat, group = group,
                                  fill = model3.e)) +
  geom_polygon(color = "white") +
  coord_equal() +
  scale_fill_distiller(palette = "RdBu")
ggplotly(map.e3)

In this case, the visual inspection makes it clear that there is an issue with spatially autocorrelated residuals, something that a test reinforces:

moran.test(Hamilton_TAZ$model3.e, Hamilton_TAZ.w)

    Moran I test under randomisation

data:  Hamilton_TAZ$model3.e  
weights: Hamilton_TAZ.w    

Moran I statistic standard deviate = 24.616, p-value < 2.2e-16
alternative hypothesis: greater
sample estimates:
Moran I statistic       Expectation          Variance 
      0.835679736      -0.003378378       0.001161885 

As seen above, the model with the full set of relevant variables resolves this problem.

Remedial action

When spatial autocorrelation is detected in the residuals, further work is warranted. The preceding examples illustrate two possible solutions to the issue of residual pattern:

  1. Modifications of the model to approximate the true functional form of the process; and
  2. Inclusion of relevant variables.

Ideally, we would try to ensure that the model is properly specified. In practice, however, it is not always evident what the functional form of the model should be. The search for an appropriate functional form can be guided by theoretical considerations, empirical findings, and experimentation. With respect to inclusion of relevant variables, it is not always possible to find all the information we desire. This could be because of limited resources, or because some aspects of the process are not known and therefore we do not even know what additional information should be collected.

In these cases, it is a fact that residual spatial autocorrelation is problematic.

Fortunately, a number of approaches have been proposed in the literature that can be used for remedial action.

In the following sections we will review some of them.

Flexible functional forms and models with spatially-varying coefficients

Some models use variable transformations to create more flexible functions, while others use adaptive estimation strategies.

Trend surface analysis

Trend surface analysis is a simple way to generate relatively flexible surfaces.

This approach consists of using the coordinates as covariates, and transforming them into polynomials of different orders. Seen this way, linear regression is the analog of a trend surface of first degree: \[ z = f(x,y) = \beta_0 + \beta_1x + \beta_2y \] where \(x\) and \(y\) are the coordinates.

A figure illustratates how the function above creates a regression plane. First, create a grid of coordinates for plotting:

df <- expand.grid(x = seq(from = -2, to = 2, by = 0.2), y = seq(from = -2, to = 2, by = 0.2))

Next, select some values for the coefficients (feel free to experiment with these values):

b0 <- 0.5 #0.5
b1 <- 1 #1
b2 <- 2 #2
z1 <- b0 + b1 * df$x + b2 * df$y
z1 <- matrix(z1, nrow = 21, ncol = 21)

The plot is as follows:

plot_ly(z = ~z1) %>% add_surface() %>%
  layout(scene = list(xaxis = list(ticktext = c("-2", "0", "2"), tickvals = c(0, 10, 20)), 
                      yaxis = list(ticktext = c("-2", "0", "2"), tickvals = c(0, 10, 20))
                      )
         )

A trend surface of second degree, or quadratic, would be as follows. Notice how it includes all possible quadratic terms, including the product \(xy\): \[ z = f(x,y) = \beta_0 + \beta_1x^2 + \beta_2x + \beta_3xy + \beta_4y + \beta_5y^2 \]

Use the same grid as above to create now a regression surface. Select some coefficients:

b0 <- 0.5 #0.5
b1 <- 2 #2
b2 <- 1 #1
b3 <- 1 #1
b4 <- 1.5 #1.5
b5 <- 0.5 #2.5
z2 <- b0 + b1 * df$x^2 + b2 * df$x + b3 * df$x * df$y + b4 * df$y + b5 * df$y^2
z2 <- matrix(z2, nrow = 21, ncol = 21)

And the plot is as follows:

plot_ly(z = ~z2) %>% add_surface() %>%
  layout(scene = list(xaxis = list(ticktext = c("-2", "0", "2"), tickvals = c(0, 10, 20)), 
                      yaxis = list(ticktext = c("-2", "0", "2"), tickvals = c(0, 10, 20))
                      )
         )

Higher order polynomials (i.e., cubic, quartic, etc.) are possible in principle. Something to keep in mind is that the higher the order of the polynomial, the more flexible the surface, which may lead to the following issues:

  1. Multicollinearity.

Powers of variables tend to be highly correlated with each other. See the following table of correlations for the x coordinate in the example:

x x^2 x^3 x^4
x 1.00 0.00 0.92 0.00
x^2 0.00 1.00 0.00 0.96
x^3 0.92 0.00 1.00 0.00
x^4 0.00 0.96 0.00 1.00

When two variables are highly collinear, the model has difficulties discriminating their relative contribution to the model. This is manifested by inflated standard errors that may depress the significance of the coefficients, and occasionally by sign reversals.

  1. Overfitting.

Overfitting is another possible consequence of using a trend surface that is too flexible. This happens when a model fits too well the observations used for callibration, but because of this it may fail to fit well new information.

To illustrate overfitting consider a simple example. Below we simulate a simple linear model with \(y_i = x_i + \epsilon_i\) (the random terms are drawn from the uniform distribution). We also simulate new data using the exact same process:

# Dataset for estimation
df.of1 <- data.frame(x = seq(from = 1, to = 10, by = 1))
df.of1 <- mutate(df.of1, y = x + runif(10, -1, 1))
# New data
new_data <- data.frame(x = seq(from = 1, to = 10, by = 0.5))
df.of2 <- mutate(new_data, y = x + runif(nrow(new_data), -1, 1))

This is the scatterplot of the observations in the estimation dataset:

p <- ggplot(data = df.of1, aes(x = x, y = y)) 
p + geom_point(size = 3)

A model with a first order trend (essentially linear regression), does not fit the observations perfectly, but when confronted with new data (plotted as red squares), it predicts them with reasonable accuracy:

mod.of1 <- lm(formula = y ~ x, data = df.of1)
pred1 <- predict(mod.of1, newdata = new_data) #mod.of1$fitted.values
p + geom_abline(slope = mod.of1$coefficients[2], intercept = mod.of1$coefficients[1], 
                color = "blue", size = 1) +
  geom_point(data = df.of2, aes(x = x, y = y), shape = 0, color = "red") +
  geom_segment(data = df.of2, aes(xend = x, yend = pred1)) + 
  geom_point(size = 3) +
  xlim(c(1, 10))

Compare to a polynomial of very high degree (nine in this case). The model is much more flexible, to the extent that it perfectly matches the observations in the estimation dataset. However, this flexibility has a downside. When the model is confronted with new information, its performance is less satisfactory.

mod.of2 <- lm(formula = y ~ poly(x, degree = 9, raw = TRUE), data = df.of1)
poly.fun <- predict(mod.of2, data.frame(x = seq(1, 10, 0.1)))
pred2 <- predict(mod.of2, newdata = new_data) #mod.of1$fitted.values
p + 
  #stat_function(fun = fun.pol, 
  geom_line(data = data.frame(x = seq(1, 10, 0.1), y = poly.fun), aes(x = x, y = y),
                color = "blue", size = 1) + 
  geom_point(data = df.of2, aes(x = x, y = y), shape = 0, color = "red") +
  geom_segment(data = df.of2, aes(xend = x, yend = pred2)) + 
  geom_point(size = 3) +
  xlim(c(1, 10))

We can compute the root mean square (RMS), for each of the two models. The RMS is a measure of error calculated as the square root of the mean of the squared differences between two values (in this case the prediction of the model and the new information). This statistic is a measure of the typical deviation between two sets of values. Given new information, the RMS would tell us the expected size of the error when making a prediction using a given model.

The RMS for model 1 is:

sqrt(mean((df.of2$y - pred1)^2))
[1] 0.525595

And for model 2:

sqrt(mean((df.of2$y - pred2)^2))
[1] 1.681143

You will notice how model 2, despite fitting the estimation data better than model 1, typically produces larger errors when new information becomes available.

  1. Edge effects.

Another consequence of overfitting, is that the resulting functions tend to display extreme behavior when taken outside of their estimation range, where the largest polynomial terms tend to dominate.

The plot below is the same high degree polynomial estimated above, just plotted in a slightly larger range of plus/minus one unit:

poly.fun <- predict(mod.of2, data.frame(x = seq(0, 11, 0.1)))
p + 
  geom_line(data = data.frame(x = seq(0, 11, 0.1), y = poly.fun), aes(x = x, y = y),
                color = "blue", size = 1) + 
  geom_point(data = df.of2, aes(x = x, y = y), shape = 0, color = "red") +
  geom_segment(data = df.of2, aes(xend = x, yend = pred2)) + 
  geom_point(size = 3)

Models with spatially varying coefficients

Another way to generate flexible functional forms is by means of models with spatially varying coefficients. Two approaches are reviewed here.

Expansion method

The expansion method (Casetti, 1972) is an approach to generate models with contextual effects. It follows a philosophy of specifying first a substantive model with variables of interest, and then an expanded model with contextual variables. In geographical analysis, typically the contextual variables are trend surfaces estimated using the coordinates of the observations.

To illustrate this, suppose that there is the following initial model of proportion of donors in a population, with two variables of substantive interest (say, income and education): \[ d_i = \beta_i(x_i,y_i) + \beta_1(x_i,y_i)I_i + \beta_3(x_i,y_i)Ed_i + \epsilon_i \]

Note how the coefficients are now a function of the coordinates at \(i\). Unlike previous models that had global coefficients, the coefficients in this model are allowed to adapt by location.

Unfortunately, it is not possible to estimate one coefficient per location. In this case, there are \(n\times k\) coefficients, which exceeds the size of the sample (\(n\)). It is not possible to retrieve more information from the sample than \(n\) parameters (this is called the incidental parameter problem.)

A possible solution is to specify a function for the coefficients, for instance, by specifying a trend surface for them: \[ \begin{array}{l} \beta_0(x_i, y_i) = \beta_{01} +\beta_{02}x_i + \beta_{03}y_i\\ \beta_1(x_i, y_i) = \beta_{11} +\beta_{12}x_i + \beta_{13}y_i\\ \beta_2(x_i, y_i) = \beta_{21} +\beta_{22}x_i + \beta_{23}y_i \end{array} \] By specifying the coefficients as a function of the coordinates, we allow them to vary by location.

Next, if we substitute these coefficients in the intial model, we arrive at a final expanded model: \[ d_i = \beta_{01} +\beta_{02}x_i + \beta_{03}y_i + \beta_{11}I_i +\beta_{12}x_iI_i + \beta_{13}y_iI_i + \beta_{21}Ed_i +\beta_{22}x_iEd_i + \beta_{23}y_iEd_i + \epsilon_i \]

This model has now nine coefficients, instead of \(n\times 3\), and can be estimated as usual.

It is important to note that since models generated based on the expansion method are based on the use of trend surfaces, similar caveats apply with respect to multicollinearity and overfitting.

Geographically weighted regression (GWR)

A different strategy to estimate models with spatially-varying coefficients is a semi-parametric approach, called geographically weighted regression (see Brunsdon et al., 1996).

Instead of selecting a functional form for the coefficients as the expansion method does, the functions are left unspecified. The spatial variation of the coefficients results from an estimation strategy that takes subsamples of the data in a systematic way.

If you recall kernel density analysis, a kernel was a way of weighting observations based on their distance from a focal point.

Geographically weighted regression applies a similar concept, with a moving window that visits a focal point and estimates a weighted least squares model at that location. The results of the regression are conventionally applied to the focal point, in such a way that not only the coefficients are localized, but also every other regression diagnostic (e.g., the coefficient of determination, the standard deviation, etc.)

A key aspect of implementing this model is the selection of the kernel bandwidth, that is, the size of the window. If the window is too large, the local models tend towards the global model (estimated using the whole sample). If the window is too small, the model tends to overfit, since in the limit each window will contain only one, or a very small number of observations.

The kernel bandwidth can be selected if we define some loss function to minimize. A conventional approach (but not the only one), is to minimize a cross-validation score of the following form: \[ CV (\delta) = \sum_{i=1}^n{\big(y_i - \hat{y}_{\neq i}(\delta)\big)^2} \] In this notation, \(\delta\) is the bandwidth, and \(\hat{y}_{\neq i}(\delta)\) is the value of \(y\) predicted by a model with a bandwidth of \(\delta\) after excluding the observation at \(i\). This is called a leave-one-out cross-validation procedure, used to prevent the estimation from shrinking the bandwidth to zero.

GWR is implemented in the package spgwr. To estimate models using this approach, the function sel.GWR, which takes as inputs a formula specifying the dependent and independent variables, a SpatialPolygonsDataFrame (or a SpatialPointsDataFrame), and the kernel function (in the example below a Gaussian kernel):

delta <- gwr.sel(formula = z ~ x + y, data = Hamilton_TAZ, gweight = gwr.Gauss)
Bandwidth: 25.59084 CV score: 399.3492 
Bandwidth: 41.36552 CV score: 418.0564 
Bandwidth: 15.84156 CV score: 363.7496 
Bandwidth: 9.816173 CV score: 323.2672 
Bandwidth: 6.092278 CV score: 300.7067 
Bandwidth: 3.790784 CV score: 306.2781 
Bandwidth: 5.801654 CV score: 299.5063 
Bandwidth: 5.313051 CV score: 298.1325 
Bandwidth: 4.731597 CV score: 298.2069 
Bandwidth: 5.045611 CV score: 297.8656 
Bandwidth: 5.040167 CV score: 297.8649 
Bandwidth: 5.020481 CV score: 297.8638 
Bandwidth: 5.022892 CV score: 297.8638 
Bandwidth: 5.022961 CV score: 297.8638 
Bandwidth: 5.023002 CV score: 297.8638 
Bandwidth: 5.022961 CV score: 297.8638 

The function gwr estimates the suite of local models given a bandwidth:

model.gwr <- gwr(formula = z ~ x + y, bandwidth = delta, data = Hamilton_TAZ, gweight = gwr.Gauss)
model.gwr
Call:
gwr(formula = z ~ x + y, data = Hamilton_TAZ, bandwidth = delta, 
    gweight = gwr.Gauss)
Kernel function: gwr.Gauss 
Fixed bandwidth: 5.022961 
Summary of GWR coefficient estimates at data points:
                 Min.  1st Qu.   Median  3rd Qu.     Max. Global
X.Intercept. -19.8637  -6.3578  -2.6342  -1.3318   1.3375 -4.248
x              7.4674  17.7597  19.7687  25.1595  38.9585 21.948
y             21.7465  33.2582  38.5066  48.8746  96.7801 46.299

The results are given for each location where a local regression was estimated. Lets append to our tidy dataframe for plotting:

Hamilton_TAZ.t <- left_join(Hamilton_TAZ.t, 
                  data.frame(GTA06 = Hamilton_TAZ$GTA06, model.gwr$SDF@data))
Joining, by = "GTA06"
Column `GTA06` joining character vector and factor, coercing into character vector
Hamilton_TAZ.t <- rename(Hamilton_TAZ.t, beta0 = X.Intercept., beta1 = x, beta2 = y)

The results can be mapped as shown below (try mapping beta1, beta2, localR2, or the residuals gwr.e):

ggplot(data = Hamilton_TAZ.t, aes(x = long, y = lat, group = group,
                                  fill = beta0)) + 
  geom_polygon(color = "white") +
  scale_fill_distiller(palette = "YlOrRd", trans = "reverse") +
  coord_equal()

You can verify that the residuals are not spatially autocorrelated:

moran.test(model.gwr$SDF$gwr.e, Hamilton_TAZ.w)

    Moran I test under randomisation

data:  model.gwr$SDF$gwr.e  
weights: Hamilton_TAZ.w    

Moran I statistic standard deviate = -0.033896, p-value = 0.5135
alternative hypothesis: greater
sample estimates:
Moran I statistic       Expectation          Variance 
     -0.004534922      -0.003378378       0.001164212 

Some caveats with respect to GWR.

Since estimation requires the selection of a kernel bandwidth, and a kernel bandwidth requires the estimation of many times leave-one-out regressions, GWR can be computationally quite demanding, especially for large datasets.

GWR has become a very popular method, however, there is conflicting evidence regarding its ability to retrieve a known spatial process, and interpretation of the spatially-varying coefficients must be conducted with a grain of salt, although this seems to be less of a concern with larger samples - but at the moment it is not known how large a sample is safe (and larger samples also become computationally more demanding). As well, the estimation method is known to be sensitive to unusual observations. At the moment, I recommend that GWR be used for prediction only, and in this respect it seems to perform as well, or even better than alternatives approaches.

Spatial Error Model (SEM)

A model that can be used to take direct remedial action with respect to residual spatial autocorrelation is the spatial error model.

This model is specified as follows: \[ y_i = \beta_0 + \sum_{j=1}^k{\beta_kx_{ij}} + \epsilon_i \]

However, it is no longer assumed that the residuals \(\epsilon\) are independent, but instead display map pattern, in the shape of a moving average: \[ \epsilon_i = \lambda\sum_{i=1}^n{w_{ij}^{st}\epsilon_i} + \mu_i \]

A second set of residuals \(\mu\) are assumed to be independent.

It is possible to show that this model is no longer linear in the coefficients (but this would require a little bit of matrix algebra). For this reason, ordinary least squares is no longer an appropriate estimation algorithm, and models of this kind are instead estimated based on maximum likelihood.

Spatial error models are implemented in the package spdep.

As a remedial model, it can account for a model with a misspecified functional form. We know that the underlying process is not linear, but we specify a linear relationship between the covariates in the form of \(z = \beta_0 + \beta_1x + \beta_2y\):

model.sem1 <- errorsarlm(formula = z ~ x + y, 
                        data = Hamilton_TAZ@data, 
                        listw = Hamilton_TAZ.w)
summary(model.sem1)

Call:errorsarlm(formula = z ~ x + y, data = Hamilton_TAZ@data, listw = Hamilton_TAZ.w)

Residuals:
      Min        1Q    Median        3Q       Max 
-2.835717 -0.844457  0.028902  0.778175  2.571815 

Type: error 
Coefficients: (asymptotic standard errors) 
            Estimate Std. Error z value  Pr(>|z|)
(Intercept)  -4.3968     0.5859 -7.5044 6.173e-14
x            21.9446     1.2605 17.4092 < 2.2e-16
y            47.2179     1.8584 25.4077 < 2.2e-16

Lambda: 0.55022, LR test value: 59.092, p-value: 1.5099e-14
Asymptotic standard error: 0.066516
    z-value: 8.2721, p-value: 2.2204e-16
Wald statistic: 68.427, p-value: < 2.22e-16

Log likelihood: -443.6038 for error model
ML residual variance (sigma squared): 1.0906, (sigma: 1.0443)
Number of observations: 297 
Number of parameters estimated: 5 
AIC: 897.21, (AIC for lm: 954.3)

The coefficient \(\lambda\) is positive (indicative of positive autocorrelation) and high, since about 50% of the moving average of the residuals \(\epsilon\) in the neighborhood of \(i\) contribute to the value of \(\epsilon_i\).

You can verify that the residuals are spatially uncorrelated (note that the alternative is “less” because of the negative sign of Moran’s I coefficient):

moran.test(model.sem1$residuals, Hamilton_TAZ.w, alternative = "less")

    Moran I test under randomisation

data:  model.sem1$residuals  
weights: Hamilton_TAZ.w    

Moran I statistic standard deviate = -0.82584, p-value = 0.2044
alternative hypothesis: less
sample estimates:
Moran I statistic       Expectation          Variance 
     -0.031552712      -0.003378378       0.001163896 

Now consider the case of a missing covariate:

model.sem2 <- errorsarlm(formula = log(z) ~ x, 
                        data = Hamilton_TAZ@data, 
                        listw = Hamilton_TAZ.w)
summary(model.sem2)

Call:errorsarlm(formula = log(z) ~ x, data = Hamilton_TAZ@data, listw = Hamilton_TAZ.w)

Residuals:
       Min         1Q     Median         3Q        Max 
-0.4014843 -0.0670803  0.0079365  0.0791249  0.4647178 

Type: error 
Coefficients: (asymptotic standard errors) 
            Estimate Std. Error z value  Pr(>|z|)
(Intercept)  1.67842    0.18291  9.1763 < 2.2e-16
x            1.92656    0.48773  3.9500 7.814e-05

Lambda: 0.91625, LR test value: 469.65, p-value: < 2.22e-16
Asymptotic standard error: 0.02273
    z-value: 40.31, p-value: < 2.22e-16
Wald statistic: 1624.9, p-value: < 2.22e-16

Log likelihood: 177.2607 for error model
ML residual variance (sigma squared): 0.013849, (sigma: 0.11768)
Number of observations: 297 
Number of parameters estimated: 4 
AIC: -346.52, (AIC for lm: 121.13)

In this case, the residual pattern is particularly strong, with more than 90% of the moving average contributing to

Alas, in this case, the remedial action falls short of cleaning the residuals, and we can see that they still remain spatially correlated:

moran.test(model.sem2$residuals, Hamilton_TAZ.w, alternative = "less")

    Moran I test under randomisation

data:  model.sem2$residuals  
weights: Hamilton_TAZ.w    

Moran I statistic standard deviate = -3.3267, p-value = 0.0004395
alternative hypothesis: less
sample estimates:
Moran I statistic       Expectation          Variance 
     -0.116544541      -0.003378378       0.001157221 

This would suggest the need for alternative action (such as the search for additional covariates).

Ideally, a model should be well-specified, and remedial action should be undertaken only when other alternatives have been exhausted.

This concludes Practice 15.

LS0tDQp0aXRsZTogIjE1IEFyZWEgRGF0YSBWSSINCm91dHB1dDogaHRtbF9ub3RlYm9vaw0KLS0tDQoNCiNJbnRyb2R1Y3Rpb24NCg0KTk9URTogVGhpcyBpcyBhbiBbUiBNYXJrZG93bl0oaHR0cDovL3JtYXJrZG93bi5yc3R1ZGlvLmNvbSkgTm90ZWJvb2suIFdoZW4geW91IGV4ZWN1dGUgY29kZSB3aXRoaW4gdGhlIG5vdGVib29rLCB0aGUgcmVzdWx0cyBhcHBlYXIgYmVuZWF0aCB0aGUgY29kZS4gDQoNCkluIHByZXZpb3VzIHByYWN0aWNlL3Nlc3Npb24sIHlvdSBsZWFybmVkIGFib3V0IGhvdyB0byB1c2UgbG9jYWwgc3BhdGlhbCBzdGF0aXN0aWNzIGZvciBleHBsb3JhdG9yeSBzcGF0aWFsIGRhdGEgYW5hbHlzaXMuIA0KDQpGb3IgdGhpcyBwcmFjdGljZSB5b3Ugd2lsbCBuZWVkIHRoZSBmb2xsb3dpbmc6DQoNCiogVGhpcyBSIG1hcmtkb3duIG5vdGVib29rLg0KKiBBIHNoYXBlIGZpbGUgY2FsbGVkICJIYW1pbHRvbiBDTUEgdHRzMDYiDQoNClRoZSBzaGFwZSBmaWxlIGluY2x1ZGVzIHNwYXRpYWwgaW5mb3JtYXRpb24gZm9yIFRyYWZmaWMgQW5hbHlzaXMgWm9uZXMgKFRBWikgaW4gdGhlIEhhbWlsdG9uIENlbnN1cyBNZXRyb3BvbGl0YW4gQXJlYSAoYXMgcG9seWdvbnMpLg0KDQojTGVhcm5pbmcgb2JqZWN0aXZlcw0KDQpJbiB0aGlzIHByYWN0aWNlLCB5b3Ugd2lsbDoNCg0KMS4gUmV2aXNpdCB0aGUgbm90aW9uIG9mIGF1dG9jb3JyZWxhdGlvbiBhcyBhIG1vZGVsIGRpYWdub3N0aWMuDQoyLiBSZW1lZGlhbCBhY3Rpb24uDQozLiBGbGV4aWJsZSBmdW5jdGlvbmFsIGZvcm1zIGFuZCBtb2RlbHMgd2l0aCBzcGF0aWFsbHktdmFyeWluZyBjb2VmZmljaWVudHMuDQogICAzLjEgVHJlbmQgc3VyZmFjZSBhbmFseXNpcy4NCiAgIDMuMiBUaGUgZXhwYW5zaW9uIG1ldGhvZC4NCiAgIDMuMyBHZW9ncmFwaGljYWxseSB3ZWlnaHRlZCByZWdyZXNzaW9uIChHV1IpLg0KNC4gU3BhdGlhbCBlcnJvciBtb2RlbCAoU0VNKS4NCg0KI1N1Z2dlc3RlZCByZWFkaW5nDQoNCk8nU3VsbGl2YW4gRCBhbmQgVW53aW4gRCAoMjAxMCkgR2VvZ3JhcGhpYyBJbmZvcm1hdGlvbiBBbmFseXNpcywgMm5kIEVkaXRpb24sIENoYXB0ZXIgNy4gSm9obiBXaWxleSAmIFNvbnM6IE5ldyBKZXJzZXkuDQoNCiNQcmVsaW1pbmFyaWVzDQoNCkFzIHVzdWFsLCBpdCBpcyBnb29kIHByYWN0aWNlIHRvIGNsZWFyIHRoZSB3b3JraW5nIHNwYWNlIHRvIG1ha2Ugc3VyZSB0aGF0IHlvdSBkbyBub3QgaGF2ZSBleHRyYW5lb3VzIGl0ZW1zIHRoZXJlIHdoZW4geW91IGJlZ2luIHlvdXIgd29yay4gVGhlIGNvbW1hbmQgaW4gUiB0byBjbGVhciB0aGUgd29ya3NwYWNlIGlzIGBybWAgKGZvciAicmVtb3ZlIiksIGZvbGxvd2VkIGJ5IGEgbGlzdCBvZiBpdGVtcyB0byBiZSByZW1vdmVkLiBUbyBjbGVhciB0aGUgd29ya3NwYWNlIGZyb20gX2FsbF8gb2JqZWN0cywgZG8gdGhlIGZvbGxvd2luZzoNCmBgYHtyfQ0Kcm0obGlzdCA9IGxzKCkpDQpgYGANCg0KTm90ZSB0aGF0IGBscygpYCBsaXN0cyBhbGwgb2JqZWN0cyBjdXJyZW50bHkgb24gdGhlIHdvcnNwYWNlLg0KDQpMb2FkIHRoZSBsaWJyYXJpZXMgeW91IHdpbGwgdXNlIGluIHRoaXMgYWN0aXZpdHk6DQpgYGB7cn0NCmxpYnJhcnkodGlkeXZlcnNlKQ0KbGlicmFyeShyZ2RhbCkNCmxpYnJhcnkoYnJvb20pDQpsaWJyYXJ5KHNwZGVwKQ0KbGlicmFyeShyZXNoYXBlMikNCmxpYnJhcnkocGxvdGx5KQ0KbGlicmFyeShrbml0cikNCmxpYnJhcnkoa2FibGVFeHRyYSkNCmxpYnJhcnkoc3Bnd3IpDQpgYGANCg0KQmVnaW4gYnkgbG9hZGluZyB0aGUgc2hhcGUgZmlsZToNCmBgYHtyfQ0KSGFtaWx0b25fVEFaIDwtIHJlYWRPR1IoIi4iLCBsYXllciA9ICJIYW1pbHRvbiBDTUEgdHRzMDYiKQ0KYGBgDQoNClRoZSBzaGFwZSBmaWxlIGluY2x1ZGVzIHRoZSBnZW9tZXRyeSBvZiB0aGUgem9uZXMgb25seS4NCg0KVG8gdXNlIHRoZSBwbG90dGluZyBmdW5jdGlvbnMgb2YgYGdncGxvdDJgLCB0aGUgYFNwYXRpYWxQb2x5Z29uRGF0YUZyYW1lYCBuZWVkcyB0byBiZSAidGlkaWVkIiBieSBtZWFucyBvZiB0aGUgYHRpZHlgIGZ1bmN0aW9uIG9mIHRoZSBgYnJvb21gIHBhY2thZ2U6DQpgYGB7cn0NCkhhbWlsdG9uX1RBWi50IDwtIHRpZHkoSGFtaWx0b25fVEFaLCByZWdpb24gPSAiR1RBMDYiKQ0KSGFtaWx0b25fVEFaLnQgPC0gZHBseXI6OnJlbmFtZShIYW1pbHRvbl9UQVoudCwgR1RBMDYgPSBpZCkNCmBgYA0KDQpUaWR5aW5nIHRoZSBzcGF0aWFsIGRhdGFmcmFtZSBzdHJpcHMgaXQgZnJvbSB0aGUgbm9uLXNwYXRpYWwgaW5mb3JtYXRpb24sIGJ1dCB3ZSBjYW4gYWRkIGFsbCB0aGUgZGF0YSBieSBtZWFucyBvZiB0aGUgYGxlZnRfam9pbmAgZnVuY3Rpb246DQpgYGB7cn0NCkhhbWlsdG9uX1RBWi50IDwtIGxlZnRfam9pbihIYW1pbHRvbl9UQVoudCwgSGFtaWx0b25fVEFaQGRhdGEsIGJ5ID0gIkdUQTA2IikNCmBgYA0KDQpOb3cgdGhlIHRpZHkgZGF0YWZyYW1lIGBIYW1pbHRvbl9EQS50YCBjb250YWlucyB0aGUgc3BhdGlhbCBpbmZvcm1hdGlvbiBhbmQgdGhlIGRhdGEuDQoNCllvdSBjYW4gcXVpY2tseSB2ZXJpZnkgdGhlIGNvbnRlbnRzIG9mIHRoZSBkYXRhZnJhbWUgYnkgbWVhbnMgb2YgYHN1bW1hcnlgOg0KYGBge3J9DQpzdW1tYXJ5KEhhbWlsdG9uX1RBWi50KQ0KYGBgDQoNCiMgUmVzaWR1YWwgc3BhdGlhbCBhdXRvY29ycmVsYXRpb24gcmV2aXNpdGVkDQoNClByZXZpb3VzbHkgeW91IGxlYXJuZWQgYWJvdXQgdGhlIHVzZSBvZiBNb3JhbidzIEkgY29lZmZpY2llbnQgYXMgYSBkaWFnbm9zdGljIGluIHJlZ3Jlc3Npb24gYW5hbHlzaXMuDQoNClJlc2lkdWFsIHNwYXRpYWwgYXV0b2NvcnJlbGF0aW9uIGlzIGEgc3ltcHRvbSBvZiBhIG1vZGVsIHRoYXQgaGFzIG5vdCBiZWVuIHByb3Blcmx5IHNwZWNpZmllZC4gVGhlcmUgYXJlIHR3byByZWFzb25zIGZvciB0aGlzIHRoYXQgYXJlIG9mIGludGVyZXN0Og0KDQoxKSBUaGUgZnVuY3Rpb25hbCBmb3JtIGlzIGluY29ycmVjdC4NCjIpIFRoZSBtb2RlbCBmYWlsZWQgdG8gaW5jbHVkZSByZWxldmFudCB2YXJpYWJsZXMuDQoNCkxldHMgZXhwbG9yZSB0aGVzZSBpbiB0dXJuLg0KDQojIyBJbmNvcnJlY3QgZnVuY3Rpb25hbCBmb3JtDQoNClRvIGlsbHVzdHJhdGUgdGhpcywgd2Ugd2lsbCBzaW11bGF0ZSBhIHNwYXRpYWwgcHJvY2VzcyBhcyBmb2xsb3dzOg0KJCQNCnogPSBmKHgseSkgPSBleHAoXGJldGFfMClleHAoXGJldGFfMXgpZXhwKFxiZXRhXzJ5KSArIFxlcHNpbG9uX2kNCiQkDQoNCkNsZWFybHksIHRoaXMgaXMgYSBub24tbGluZWFyIHNwYXRpYWwgcHJvY2Vzcy4NCg0KVGhlIHNpbXVsYXRpb24gaXMgYXMgZm9sbG93cywgd2l0aCBhIHJhbmRvbSB0ZXJtIHdpdGggYSBtZWFuIG9mIHplcm8gYW5kIHN0YW5kYXJkIGRldmlhdGlvbiBvZiAxLiAqKlRoZSByYW5kb20gdGVybXMgYXJlIGluZGVwZW5kZW50IGJ5IGRlc2lnbioqOg0KYGBge3J9DQpzZXQuc2VlZCgxMCkNCmIwID0gMQ0KYjEgPSAyDQpiMiA9IDQNCnh5X2Nvb3JkcyA8LSBjb29yZGluYXRlcyhIYW1pbHRvbl9UQVopDQpIYW1pbHRvbl9UQVpAZGF0YSA8LSBtdXRhdGUoSGFtaWx0b25fVEFaQGRhdGEsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgeCA9IHh5X2Nvb3Jkc1ssMV0gLSBtaW4oeHlfY29vcmRzWywxXSksDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgeSA9IHh5X2Nvb3Jkc1ssMl0gLSBtaW4oeHlfY29vcmRzWywyXSksDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgeiA9IGV4cChiMCkgKiBleHAoYjEgKiB4KSAqIGV4cChiMiAqIHkpICsNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJub3JtKG4gPSAyOTcsIG1lYW4gPSAwLCBzZCA9IDEpKQ0Kc3VtbWFyeShIYW1pbHRvbl9UQVpAZGF0YVssMTM6MTVdKQ0KYGBgDQoNClN1cHBvc2UgdGhhdCB3ZSBlc3RpbWF0ZSB0aGUgbW9kZWwgYXMgYSBsaW5lYXIgcmVncmVzc2lvbiB0aGF0IGRvZXMgbm90IGNvcnJlY3RseSBjYXB0dXJlIHRoZSBub24tbGluZWFyaXR5LiBUaGUgbW9kZWwgd291bGQgYmUgYXMgZm9sbG93czoNCmBgYHtyfQ0KbW9kZWwxIDwtIGxtKGZvcm11bGEgPSB6IH4geCArIHksIGRhdGEgPSBIYW1pbHRvbl9UQVpAZGF0YSkgDQpzdW1tYXJ5KG1vZGVsMSkNCmBgYA0KDQpBdCBmaXJzdCBnbGFuY2UsIHRoZSBtb2RlbCBnaXZlcyB0aGUgaW1wcmVzc2lvbiBvZiBhIHZlcnkgZ29vZCBmaXQ6IGFsbCBjb2VmZmljaWVudHMgYXJlIHNpZ25pZmljYW50LCBhbmQgdGhlIGNvZWZmaWNpZW50IG9mIG11bHRpcGxlIGRldGVybWluYXRpb24gJFJeMiQgaXMgdmVyeSBoaWdoLg0KDQpBdCB0aGlzIHBvaW50LCBpdCBpcyBpbXBvcnRhbnQgdG8gZXhhbWluZSB0aGUgcmVzaWR1YWxzIHRvIHZlcmlmeSB0aGF0IHRoZXkgYXJlIGluZGVwZW5kZW50LiBMZXRzIGFkZCB0aGUgcmVzaWR1YWxzIG9mIHRoaXMgbW9kZWwgdG8geW91ciBkYXRhZnJhbWVzOg0KYGBge3J9DQpIYW1pbHRvbl9UQVpAZGF0YSRtb2RlbDEuZSA8LSBtb2RlbDEkcmVzaWR1YWxzDQpIYW1pbHRvbl9UQVoudCA8LSBsZWZ0X2pvaW4oSGFtaWx0b25fVEFaLnQsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgZGF0YS5mcmFtZShHVEEwNiA9IEhhbWlsdG9uX1RBWiRHVEEwNiwgbW9kZWwxJHJlc2lkdWFscykpDQpIYW1pbHRvbl9UQVoudCA8LSByZW5hbWUoSGFtaWx0b25fVEFaLnQsIG1vZGVsMS5lID0gbW9kZWwxLnJlc2lkdWFscykNCmBgYA0KDQpBIG1hcCBvZiB0aGUgcmVzaWR1YWxzIGNhbiBoZWxwIGV4YW1pbmUgdGhlaXIgc3BhdGlhbCBwYXR0ZXJuOg0KYGBge3J9DQptYXAuZTEgPC0gZ2dwbG90KGRhdGEgPSBIYW1pbHRvbl9UQVoudCwgYWVzKHggPSBsb25nLCB5ID0gbGF0LCBncm91cCA9IGdyb3VwLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZpbGwgPSBtb2RlbDEuZSkpICsNCiAgZ2VvbV9wb2x5Z29uKGNvbG9yID0gIndoaXRlIikgKw0KICBjb29yZF9lcXVhbCgpICsNCiAgc2NhbGVfZmlsbF9kaXN0aWxsZXIocGFsZXR0ZSA9ICJSZEJ1IikNCmdncGxvdGx5KG1hcC5lMSkNCmBgYA0KDQpUbyB0ZXN0IHRoZSByZXNpZHVhbHMgZm9yIHNwYXRpYWwgYXV0b2NvcnJlbGF0aW9uIHdlIGZpcnN0IGNyZWF0ZSBhIHNldCBvZiBzcGF0aWFsIHdlaWdodHM6DQpgYGB7cn0NCkhhbWlsdG9uX1RBWi53IDwtIG5iMmxpc3R3KHBvbHkybmIoSGFtaWx0b25fVEFaKSkNCmBgYA0KDQpXaXRoIHRoaXMsIHdlIGNhbiBub3cgY2FsY3VsYXRlIE1vcmFuJ3MgSToNCmBgYHtyfQ0KbW9yYW4udGVzdChIYW1pbHRvbl9UQVokbW9kZWwxLmUsIEhhbWlsdG9uX1RBWi53KQ0KYGBgDQoNClRoZSB0ZXN0IGRvZXMgbm90IGFsbG93IHVzIHRvIHJlamVjdCB0aGUgbnVsbCBoeXBvdGhlc2lzIG9mIHNwYXRpYWwgaW5kZXBlbmRlbmNlLiBUaHVzLCBkZXNwaXRlIHRoZSBhcHBhcmVudCBnb29kbmVzcyBvZiBmaXQgb2YgdGhlIG1vZGVsLCB0aGVyZSBpcyByZWFzb24gdG8gYmVsaWV2ZSBzb21ldGhpbmcgaXMgbWlzc2luZy4NCg0KTGV0cyBub3cgdXNlIGEgdmFyaWFibGUgdHJhbnNmb3JtYXRpb24gdG8gYXBwcm94aW1hdGUgdGhlIHVuZGVybHlpbmcgbm9uLWxpbmVhciBwcm9jZXNzOg0KYGBge3J9DQptb2RlbDIgPC0gbG0oZm9ybXVsYSA9IGxvZyh6KSB+IHggKyB5LCBkYXRhID0gSGFtaWx0b25fVEFaQGRhdGEpDQpzdW1tYXJ5KG1vZGVsMikNCmBgYA0KDQpUaGlzIG1vZGVsIGRvZXMgbm90IG5lY2Vzc2FyaWx5IGhhdmUgYSBiZXR0ZXIgZ29vZG5lc3Mgb2YgZml0LiBIb3dldmVyLCB3aGVuIHdlIHRlc3QgZm9yIHNwYXRpYWwgYXV0b2NvcnJlbGF0aW9uOg0KYGBge3J9DQpIYW1pbHRvbl9UQVpAZGF0YSRtb2RlbDIuZSA8LSBtb2RlbDIkcmVzaWR1YWxzDQptb3Jhbi50ZXN0KEhhbWlsdG9uX1RBWiRtb2RlbDIuZSwgSGFtaWx0b25fVEFaLncpDQpgYGANCg0KT25jZSB0aGF0IHRoZSBjb3JyZWN0IGZ1bmN0aW9uYWwgZm9ybSBoYXMgYmVlbiBzcGVjaWZpZWQsIHRoZSBtb2RlbCBpcyBiZXR0ZXIgYXQgY2FwdHVyaW5nIHRoZSB1bmRlcmx5aW5nIHByb2Nlc3MgKGNoZWNrIGhvdyB0aGUgY29lZmZpY2llbnRzIGFwcHJveGltYXRlIHRvIGEgaGlnaCBkZWdyZWUgdGhlIHRydWUgY29lZmZpY2llbnRzIG9mIHRoZSBtb2RlbCkuIEluIGFkZGl0aW9uLCB3ZSBjYW4gY29uY2x1ZGUgdGhhdCB0aGUgcmVzaWR1YWxzIGFyZSBpbmRlcGVuZGVudCwgYW5kIHRoZXJlZm9yZSBhcmUgbm93IGFsc28gc3BhdGlhbGx5IHJhbmRvbTogbWVhbmluZyB0aGUgdGhlcmUgaXMgbm90aGluZyBsZWZ0IG9mIHRoZSBwcm9jZXNzIGJ1dCB3aGl0ZSBub2lzZS4NCg0KIyMgT21pdHRlZCB2YXJpYWJsZXMNCg0KVXNpbmcgdGhlIHNhbWUgZXhhbXBsZSwgc3VwcG9zZSBub3cgdGhhdCB0aGUgZnVuY3Rpb24gZm9ybSBpcyBjb3JyZWN0bHkgc3BlY2lmaWVkLCBidXQgYSByZWxldmFudCB2YXJpYWJsZSBpcyBtaXNzaW5nOg0KYGBge3J9DQptb2RlbDMgPC0gbG0oZm9ybXVsYSA9IGxvZyh6KSB+IHgsIGRhdGEgPSBIYW1pbHRvbl9UQVpAZGF0YSkNCnN1bW1hcnkobW9kZWwzKQ0KYGBgDQoNCkFzIGJlZm9yZSwgbGV0cyBhcHBlbmQgdGhlIHJlc2lkdWFscyB0byB0aGUgZGF0YWZyYW1lczoNCmBgYHtyfQ0KSGFtaWx0b25fVEFaQGRhdGEkbW9kZWwzLmUgPC0gbW9kZWwzJHJlc2lkdWFscw0KSGFtaWx0b25fVEFaLnQgPC0gbGVmdF9qb2luKEhhbWlsdG9uX1RBWi50LCANCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGRhdGEuZnJhbWUoR1RBMDYgPSBIYW1pbHRvbl9UQVokR1RBMDYsIG1vZGVsMyRyZXNpZHVhbHMpKQ0KSGFtaWx0b25fVEFaLnQgPC0gcmVuYW1lKEhhbWlsdG9uX1RBWi50LCBtb2RlbDMuZSA9IG1vZGVsMy5yZXNpZHVhbHMpDQpgYGANCg0KQSBtYXAgb2YgdGhlIHJlc2lkdWFscyBjYW4gaGVscCBleGFtaW5lIHRoZWlyIHNwYXRpYWwgcGF0dGVybjoNCmBgYHtyfQ0KbWFwLmUzIDwtIGdncGxvdChkYXRhID0gSGFtaWx0b25fVEFaLnQsIGFlcyh4ID0gbG9uZywgeSA9IGxhdCwgZ3JvdXAgPSBncm91cCwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmaWxsID0gbW9kZWwzLmUpKSArDQogIGdlb21fcG9seWdvbihjb2xvciA9ICJ3aGl0ZSIpICsNCiAgY29vcmRfZXF1YWwoKSArDQogIHNjYWxlX2ZpbGxfZGlzdGlsbGVyKHBhbGV0dGUgPSAiUmRCdSIpDQpnZ3Bsb3RseShtYXAuZTMpDQpgYGANCg0KSW4gdGhpcyBjYXNlLCB0aGUgdmlzdWFsIGluc3BlY3Rpb24gbWFrZXMgaXQgY2xlYXIgdGhhdCB0aGVyZSBpcyBhbiBpc3N1ZSB3aXRoIHNwYXRpYWxseSBhdXRvY29ycmVsYXRlZCByZXNpZHVhbHMsIHNvbWV0aGluZyB0aGF0IGEgdGVzdCByZWluZm9yY2VzOg0KYGBge3J9DQptb3Jhbi50ZXN0KEhhbWlsdG9uX1RBWiRtb2RlbDMuZSwgSGFtaWx0b25fVEFaLncpDQpgYGANCg0KQXMgc2VlbiBhYm92ZSwgdGhlIG1vZGVsIHdpdGggdGhlIGZ1bGwgc2V0IG9mIHJlbGV2YW50IHZhcmlhYmxlcyByZXNvbHZlcyB0aGlzIHByb2JsZW0uDQoNCiMgUmVtZWRpYWwgYWN0aW9uDQoNCldoZW4gc3BhdGlhbCBhdXRvY29ycmVsYXRpb24gaXMgZGV0ZWN0ZWQgaW4gdGhlIHJlc2lkdWFscywgZnVydGhlciB3b3JrIGlzIHdhcnJhbnRlZC4gVGhlIHByZWNlZGluZyBleGFtcGxlcyBpbGx1c3RyYXRlIHR3byBwb3NzaWJsZSBzb2x1dGlvbnMgdG8gdGhlIGlzc3VlIG9mIHJlc2lkdWFsIHBhdHRlcm46IA0KDQoxLiBNb2RpZmljYXRpb25zIG9mIHRoZSBtb2RlbCB0byBhcHByb3hpbWF0ZSB0aGUgdHJ1ZSBmdW5jdGlvbmFsIGZvcm0gb2YgdGhlIHByb2Nlc3M7IGFuZA0KMi4gSW5jbHVzaW9uIG9mIHJlbGV2YW50IHZhcmlhYmxlcy4NCg0KSWRlYWxseSwgd2Ugd291bGQgdHJ5IHRvIGVuc3VyZSB0aGF0IHRoZSBtb2RlbCBpcyBwcm9wZXJseSBzcGVjaWZpZWQuIEluIHByYWN0aWNlLCBob3dldmVyLCBpdCBpcyBub3QgYWx3YXlzIGV2aWRlbnQgd2hhdCB0aGUgZnVuY3Rpb25hbCBmb3JtIG9mIHRoZSBtb2RlbCBzaG91bGQgYmUuIFRoZSBzZWFyY2ggZm9yIGFuIGFwcHJvcHJpYXRlIGZ1bmN0aW9uYWwgZm9ybSBjYW4gYmUgZ3VpZGVkIGJ5IHRoZW9yZXRpY2FsIGNvbnNpZGVyYXRpb25zLCBlbXBpcmljYWwgZmluZGluZ3MsIGFuZCBleHBlcmltZW50YXRpb24uIFdpdGggcmVzcGVjdCB0byBpbmNsdXNpb24gb2YgcmVsZXZhbnQgdmFyaWFibGVzLCBpdCBpcyBub3QgYWx3YXlzIHBvc3NpYmxlIHRvIGZpbmQgYWxsIHRoZSBpbmZvcm1hdGlvbiB3ZSBkZXNpcmUuIFRoaXMgY291bGQgYmUgYmVjYXVzZSBvZiBsaW1pdGVkIHJlc291cmNlcywgb3IgYmVjYXVzZSBzb21lIGFzcGVjdHMgb2YgdGhlIHByb2Nlc3MgYXJlIG5vdCBrbm93biBhbmQgdGhlcmVmb3JlIHdlIGRvIG5vdCBldmVuIGtub3cgd2hhdCBhZGRpdGlvbmFsIGluZm9ybWF0aW9uIHNob3VsZCBiZSBjb2xsZWN0ZWQuDQoNCkluIHRoZXNlIGNhc2VzLCBpdCBpcyBhIGZhY3QgdGhhdCByZXNpZHVhbCBzcGF0aWFsIGF1dG9jb3JyZWxhdGlvbiBpcyBwcm9ibGVtYXRpYy4NCg0KRm9ydHVuYXRlbHksIGEgbnVtYmVyIG9mIGFwcHJvYWNoZXMgaGF2ZSBiZWVuIHByb3Bvc2VkIGluIHRoZSBsaXRlcmF0dXJlIHRoYXQgY2FuIGJlIHVzZWQgZm9yIHJlbWVkaWFsIGFjdGlvbi4NCg0KSW4gdGhlIGZvbGxvd2luZyBzZWN0aW9ucyB3ZSB3aWxsIHJldmlldyBzb21lIG9mIHRoZW0uDQoNCiMgRmxleGlibGUgZnVuY3Rpb25hbCBmb3JtcyBhbmQgbW9kZWxzIHdpdGggc3BhdGlhbGx5LXZhcnlpbmcgY29lZmZpY2llbnRzDQoNClNvbWUgbW9kZWxzIHVzZSB2YXJpYWJsZSB0cmFuc2Zvcm1hdGlvbnMgdG8gY3JlYXRlIG1vcmUgZmxleGlibGUgZnVuY3Rpb25zLCB3aGlsZSBvdGhlcnMgdXNlIGFkYXB0aXZlIGVzdGltYXRpb24gc3RyYXRlZ2llcy4NCg0KIyMgVHJlbmQgc3VyZmFjZSBhbmFseXNpcw0KDQpUcmVuZCBzdXJmYWNlIGFuYWx5c2lzIGlzIGEgc2ltcGxlIHdheSB0byBnZW5lcmF0ZSByZWxhdGl2ZWx5IGZsZXhpYmxlIHN1cmZhY2VzLg0KDQpUaGlzIGFwcHJvYWNoIGNvbnNpc3RzIG9mIHVzaW5nIHRoZSBjb29yZGluYXRlcyBhcyBjb3ZhcmlhdGVzLCBhbmQgdHJhbnNmb3JtaW5nIHRoZW0gaW50byBwb2x5bm9taWFscyBvZiBkaWZmZXJlbnQgb3JkZXJzLiBTZWVuIHRoaXMgd2F5LCBsaW5lYXIgcmVncmVzc2lvbiBpcyB0aGUgYW5hbG9nIG9mIGEgdHJlbmQgc3VyZmFjZSBvZiBmaXJzdCBkZWdyZWU6DQokJA0KeiA9IGYoeCx5KSA9IFxiZXRhXzAgKyBcYmV0YV8xeCArIFxiZXRhXzJ5DQokJA0Kd2hlcmUgJHgkIGFuZCAkeSQgYXJlIHRoZSBjb29yZGluYXRlcy4NCg0KQSBmaWd1cmUgaWxsdXN0cmF0YXRlcyBob3cgdGhlIGZ1bmN0aW9uIGFib3ZlIGNyZWF0ZXMgYSByZWdyZXNzaW9uIF9wbGFuZV8uIEZpcnN0LCBjcmVhdGUgYSBncmlkIG9mIGNvb3JkaW5hdGVzIGZvciBwbG90dGluZzoNCmBgYHtyfQ0KZGYgPC0gZXhwYW5kLmdyaWQoeCA9IHNlcShmcm9tID0gLTIsIHRvID0gMiwgYnkgPSAwLjIpLCB5ID0gc2VxKGZyb20gPSAtMiwgdG8gPSAyLCBieSA9IDAuMikpDQpgYGANCg0KTmV4dCwgc2VsZWN0IHNvbWUgdmFsdWVzIGZvciB0aGUgY29lZmZpY2llbnRzIChmZWVsIGZyZWUgdG8gZXhwZXJpbWVudCB3aXRoIHRoZXNlIHZhbHVlcyk6DQpgYGB7cn0NCmIwIDwtIDAuNSAjMC41DQpiMSA8LSAxICMxDQpiMiA8LSAyICMyDQp6MSA8LSBiMCArIGIxICogZGYkeCArIGIyICogZGYkeQ0KejEgPC0gbWF0cml4KHoxLCBucm93ID0gMjEsIG5jb2wgPSAyMSkNCmBgYA0KDQpUaGUgcGxvdCBpcyBhcyBmb2xsb3dzOg0KYGBge3J9DQpwbG90X2x5KHogPSB+ejEpICU+JSBhZGRfc3VyZmFjZSgpICU+JQ0KICBsYXlvdXQoc2NlbmUgPSBsaXN0KHhheGlzID0gbGlzdCh0aWNrdGV4dCA9IGMoIi0yIiwgIjAiLCAiMiIpLCB0aWNrdmFscyA9IGMoMCwgMTAsIDIwKSksIA0KICAgICAgICAgICAgICAgICAgICAgIHlheGlzID0gbGlzdCh0aWNrdGV4dCA9IGMoIi0yIiwgIjAiLCAiMiIpLCB0aWNrdmFscyA9IGMoMCwgMTAsIDIwKSkNCiAgICAgICAgICAgICAgICAgICAgICApDQogICAgICAgICApDQpgYGANCg0KQSB0cmVuZCBzdXJmYWNlIG9mIHNlY29uZCBkZWdyZWUsIG9yIHF1YWRyYXRpYywgd291bGQgYmUgYXMgZm9sbG93cy4gTm90aWNlIGhvdyBpdCBpbmNsdWRlcyBfYWxsXyBwb3NzaWJsZSBxdWFkcmF0aWMgdGVybXMsIGluY2x1ZGluZyB0aGUgcHJvZHVjdCAkeHkkOg0KJCQNCnogPSBmKHgseSkgPSBcYmV0YV8wICsgXGJldGFfMXheMiArIFxiZXRhXzJ4ICsgXGJldGFfM3h5ICsgXGJldGFfNHkgKyBcYmV0YV81eV4yDQokJA0KDQpVc2UgdGhlIHNhbWUgZ3JpZCBhcyBhYm92ZSB0byBjcmVhdGUgbm93IGEgcmVncmVzc2lvbiBfc3VyZmFjZV8uIFNlbGVjdCBzb21lIGNvZWZmaWNpZW50czoNCmBgYHtyfQ0KYjAgPC0gMC41ICMwLjUNCmIxIDwtIDIgIzINCmIyIDwtIDEgIzENCmIzIDwtIDEgIzENCmI0IDwtIDEuNSAjMS41DQpiNSA8LSAwLjUgIzIuNQ0KejIgPC0gYjAgKyBiMSAqIGRmJHheMiArIGIyICogZGYkeCArIGIzICogZGYkeCAqIGRmJHkgKyBiNCAqIGRmJHkgKyBiNSAqIGRmJHleMg0KejIgPC0gbWF0cml4KHoyLCBucm93ID0gMjEsIG5jb2wgPSAyMSkNCmBgYA0KDQpBbmQgdGhlIHBsb3QgaXMgYXMgZm9sbG93czoNCmBgYHtyfQ0KcGxvdF9seSh6ID0gfnoyKSAlPiUgYWRkX3N1cmZhY2UoKSAlPiUNCiAgbGF5b3V0KHNjZW5lID0gbGlzdCh4YXhpcyA9IGxpc3QodGlja3RleHQgPSBjKCItMiIsICIwIiwgIjIiKSwgdGlja3ZhbHMgPSBjKDAsIDEwLCAyMCkpLCANCiAgICAgICAgICAgICAgICAgICAgICB5YXhpcyA9IGxpc3QodGlja3RleHQgPSBjKCItMiIsICIwIiwgIjIiKSwgdGlja3ZhbHMgPSBjKDAsIDEwLCAyMCkpDQogICAgICAgICAgICAgICAgICAgICAgKQ0KICAgICAgICAgKQ0KYGBgDQoNCkhpZ2hlciBvcmRlciBwb2x5bm9taWFscyAoaS5lLiwgY3ViaWMsIHF1YXJ0aWMsIGV0Yy4pIGFyZSBwb3NzaWJsZSBpbiBwcmluY2lwbGUuIFNvbWV0aGluZyB0byBrZWVwIGluIG1pbmQgaXMgdGhhdCB0aGUgaGlnaGVyIHRoZSBvcmRlciBvZiB0aGUgcG9seW5vbWlhbCwgdGhlIG1vcmUgZmxleGlibGUgdGhlIHN1cmZhY2UsIHdoaWNoIG1heSBsZWFkIHRvIHRoZSBmb2xsb3dpbmcgaXNzdWVzOg0KDQoxLiBNdWx0aWNvbGxpbmVhcml0eS4NCg0KUG93ZXJzIG9mIHZhcmlhYmxlcyB0ZW5kIHRvIGJlIGhpZ2hseSBjb3JyZWxhdGVkIHdpdGggZWFjaCBvdGhlci4gU2VlIHRoZSBmb2xsb3dpbmcgdGFibGUgb2YgY29ycmVsYXRpb25zIGZvciB0aGUgYHhgIGNvb3JkaW5hdGUgaW4gdGhlIGV4YW1wbGU6DQpgYGB7ciBlY2hvID0gRkFMU0UsIHJlc3VsdHMgPSAiYXNpcyJ9DQprYWJsZShjb3IoY2JpbmQoeCA9IGRmJHgsIGB4XjJgID0gZGYkeF4yLCBgeF4zYCA9IGRmJHheMywgYHheNGAgPSBkZiR4XjQpKSwgDQogICAgICBkaWdpdHMgPSAyLCBmb3JtYXQgPSAiaHRtbCIpICU+JSBrYWJsZV9zdHlsaW5nKCkNCmBgYA0KDQpXaGVuIHR3byB2YXJpYWJsZXMgYXJlIGhpZ2hseSBjb2xsaW5lYXIsIHRoZSBtb2RlbCBoYXMgZGlmZmljdWx0aWVzIGRpc2NyaW1pbmF0aW5nIHRoZWlyIHJlbGF0aXZlIGNvbnRyaWJ1dGlvbiB0byB0aGUgbW9kZWwuIFRoaXMgaXMgbWFuaWZlc3RlZCBieSBpbmZsYXRlZCBzdGFuZGFyZCBlcnJvcnMgdGhhdCBtYXkgZGVwcmVzcyB0aGUgc2lnbmlmaWNhbmNlIG9mIHRoZSBjb2VmZmljaWVudHMsIGFuZCBvY2Nhc2lvbmFsbHkgYnkgc2lnbiByZXZlcnNhbHMuDQoNCjIuIE92ZXJmaXR0aW5nLg0KDQpPdmVyZml0dGluZyBpcyBhbm90aGVyIHBvc3NpYmxlIGNvbnNlcXVlbmNlIG9mIHVzaW5nIGEgdHJlbmQgc3VyZmFjZSB0aGF0IGlzIHRvbyBmbGV4aWJsZS4gVGhpcyBoYXBwZW5zIHdoZW4gYSBtb2RlbCBmaXRzIHRvbyB3ZWxsIHRoZSBvYnNlcnZhdGlvbnMgdXNlZCBmb3IgY2FsbGlicmF0aW9uLCBidXQgYmVjYXVzZSBvZiB0aGlzIGl0IG1heSBmYWlsIHRvIGZpdCB3ZWxsIG5ldyBpbmZvcm1hdGlvbi4NCg0KVG8gaWxsdXN0cmF0ZSBvdmVyZml0dGluZyBjb25zaWRlciBhIHNpbXBsZSBleGFtcGxlLiBCZWxvdyB3ZSBzaW11bGF0ZSBhIHNpbXBsZSBsaW5lYXIgbW9kZWwgd2l0aCAkeV9pID0gIHhfaSArIFxlcHNpbG9uX2kkICh0aGUgcmFuZG9tIHRlcm1zIGFyZSBkcmF3biBmcm9tIHRoZSB1bmlmb3JtIGRpc3RyaWJ1dGlvbikuIFdlIGFsc28gc2ltdWxhdGUgbmV3IGRhdGEgdXNpbmcgdGhlIGV4YWN0IHNhbWUgcHJvY2VzczoNCmBgYHtyfQ0KIyBEYXRhc2V0IGZvciBlc3RpbWF0aW9uDQpkZi5vZjEgPC0gZGF0YS5mcmFtZSh4ID0gc2VxKGZyb20gPSAxLCB0byA9IDEwLCBieSA9IDEpKQ0KZGYub2YxIDwtIG11dGF0ZShkZi5vZjEsIHkgPSB4ICsgcnVuaWYoMTAsIC0xLCAxKSkNCiMgTmV3IGRhdGENCm5ld19kYXRhIDwtIGRhdGEuZnJhbWUoeCA9IHNlcShmcm9tID0gMSwgdG8gPSAxMCwgYnkgPSAwLjUpKQ0KZGYub2YyIDwtIG11dGF0ZShuZXdfZGF0YSwgeSA9IHggKyBydW5pZihucm93KG5ld19kYXRhKSwgLTEsIDEpKQ0KYGBgDQoNClRoaXMgaXMgdGhlIHNjYXR0ZXJwbG90IG9mIHRoZSBvYnNlcnZhdGlvbnMgaW4gdGhlIGVzdGltYXRpb24gZGF0YXNldDoNCmBgYHtyfQ0KcCA8LSBnZ3Bsb3QoZGF0YSA9IGRmLm9mMSwgYWVzKHggPSB4LCB5ID0geSkpIA0KcCArIGdlb21fcG9pbnQoc2l6ZSA9IDMpDQpgYGANCg0KQSBtb2RlbCB3aXRoIGEgZmlyc3Qgb3JkZXIgdHJlbmQgKGVzc2VudGlhbGx5IGxpbmVhciByZWdyZXNzaW9uKSwgZG9lcyBub3QgZml0IHRoZSBvYnNlcnZhdGlvbnMgcGVyZmVjdGx5LCBidXQgd2hlbiBjb25mcm9udGVkIHdpdGggbmV3IGRhdGEgKHBsb3R0ZWQgYXMgcmVkIHNxdWFyZXMpLCBpdCBwcmVkaWN0cyB0aGVtIHdpdGggcmVhc29uYWJsZSBhY2N1cmFjeToNCmBgYHtyfQ0KbW9kLm9mMSA8LSBsbShmb3JtdWxhID0geSB+IHgsIGRhdGEgPSBkZi5vZjEpDQpwcmVkMSA8LSBwcmVkaWN0KG1vZC5vZjEsIG5ld2RhdGEgPSBuZXdfZGF0YSkgI21vZC5vZjEkZml0dGVkLnZhbHVlcw0KcCArIGdlb21fYWJsaW5lKHNsb3BlID0gbW9kLm9mMSRjb2VmZmljaWVudHNbMl0sIGludGVyY2VwdCA9IG1vZC5vZjEkY29lZmZpY2llbnRzWzFdLCANCiAgICAgICAgICAgICAgICBjb2xvciA9ICJibHVlIiwgc2l6ZSA9IDEpICsNCiAgZ2VvbV9wb2ludChkYXRhID0gZGYub2YyLCBhZXMoeCA9IHgsIHkgPSB5KSwgc2hhcGUgPSAwLCBjb2xvciA9ICJyZWQiKSArDQogIGdlb21fc2VnbWVudChkYXRhID0gZGYub2YyLCBhZXMoeGVuZCA9IHgsIHllbmQgPSBwcmVkMSkpICsgDQogIGdlb21fcG9pbnQoc2l6ZSA9IDMpICsNCiAgeGxpbShjKDEsIDEwKSkNCmBgYA0KDQpDb21wYXJlIHRvIGEgcG9seW5vbWlhbCBvZiB2ZXJ5IGhpZ2ggZGVncmVlIChuaW5lIGluIHRoaXMgY2FzZSkuIFRoZSBtb2RlbCBpcyBtdWNoIG1vcmUgZmxleGlibGUsIHRvIHRoZSBleHRlbnQgdGhhdCBpdCBwZXJmZWN0bHkgbWF0Y2hlcyB0aGUgb2JzZXJ2YXRpb25zIGluIHRoZSBlc3RpbWF0aW9uIGRhdGFzZXQuIEhvd2V2ZXIsIHRoaXMgZmxleGliaWxpdHkgaGFzIGEgZG93bnNpZGUuIFdoZW4gdGhlIG1vZGVsIGlzIGNvbmZyb250ZWQgd2l0aCBuZXcgaW5mb3JtYXRpb24sIGl0cyBwZXJmb3JtYW5jZSBpcyBsZXNzIHNhdGlzZmFjdG9yeS4NCmBgYHtyfQ0KbW9kLm9mMiA8LSBsbShmb3JtdWxhID0geSB+IHBvbHkoeCwgZGVncmVlID0gOSwgcmF3ID0gVFJVRSksIGRhdGEgPSBkZi5vZjEpDQpwb2x5LmZ1biA8LSBwcmVkaWN0KG1vZC5vZjIsIGRhdGEuZnJhbWUoeCA9IHNlcSgxLCAxMCwgMC4xKSkpDQpwcmVkMiA8LSBwcmVkaWN0KG1vZC5vZjIsIG5ld2RhdGEgPSBuZXdfZGF0YSkgI21vZC5vZjEkZml0dGVkLnZhbHVlcw0KDQpwICsgDQogICNzdGF0X2Z1bmN0aW9uKGZ1biA9IGZ1bi5wb2wsIA0KICBnZW9tX2xpbmUoZGF0YSA9IGRhdGEuZnJhbWUoeCA9IHNlcSgxLCAxMCwgMC4xKSwgeSA9IHBvbHkuZnVuKSwgYWVzKHggPSB4LCB5ID0geSksDQogICAgICAgICAgICAgICAgY29sb3IgPSAiYmx1ZSIsIHNpemUgPSAxKSArIA0KICBnZW9tX3BvaW50KGRhdGEgPSBkZi5vZjIsIGFlcyh4ID0geCwgeSA9IHkpLCBzaGFwZSA9IDAsIGNvbG9yID0gInJlZCIpICsNCiAgZ2VvbV9zZWdtZW50KGRhdGEgPSBkZi5vZjIsIGFlcyh4ZW5kID0geCwgeWVuZCA9IHByZWQyKSkgKyANCiAgZ2VvbV9wb2ludChzaXplID0gMykgKw0KICB4bGltKGMoMSwgMTApKQ0KYGBgDQoNCldlIGNhbiBjb21wdXRlIHRoZSBfcm9vdCBtZWFuIHNxdWFyZV8gKFJNUyksIGZvciBlYWNoIG9mIHRoZSB0d28gbW9kZWxzLiBUaGUgUk1TIGlzIGEgbWVhc3VyZSBvZiBlcnJvciBjYWxjdWxhdGVkIGFzIHRoZSBzcXVhcmUgcm9vdCBvZiB0aGUgbWVhbiBvZiB0aGUgc3F1YXJlZCBkaWZmZXJlbmNlcyBiZXR3ZWVuIHR3byB2YWx1ZXMgKGluIHRoaXMgY2FzZSB0aGUgcHJlZGljdGlvbiBvZiB0aGUgbW9kZWwgYW5kIHRoZSBuZXcgaW5mb3JtYXRpb24pLiBUaGlzIHN0YXRpc3RpYyBpcyBhIG1lYXN1cmUgb2YgdGhlIHR5cGljYWwgZGV2aWF0aW9uIGJldHdlZW4gdHdvIHNldHMgb2YgdmFsdWVzLiBHaXZlbiBuZXcgaW5mb3JtYXRpb24sIHRoZSBSTVMgd291bGQgdGVsbCB1cyB0aGUgZXhwZWN0ZWQgc2l6ZSBvZiB0aGUgZXJyb3Igd2hlbiBtYWtpbmcgYSBwcmVkaWN0aW9uIHVzaW5nIGEgZ2l2ZW4gbW9kZWwuDQoNClRoZSBSTVMgZm9yIG1vZGVsIDEgaXM6DQpgYGB7cn0NCnNxcnQobWVhbigoZGYub2YyJHkgLSBwcmVkMSleMikpDQpgYGANCg0KQW5kIGZvciBtb2RlbCAyOg0KYGBge3J9DQpzcXJ0KG1lYW4oKGRmLm9mMiR5IC0gcHJlZDIpXjIpKQ0KYGBgDQoNCllvdSB3aWxsIG5vdGljZSBob3cgbW9kZWwgMiwgZGVzcGl0ZSBmaXR0aW5nIHRoZSBlc3RpbWF0aW9uIGRhdGEgYmV0dGVyIHRoYW4gbW9kZWwgMSwgdHlwaWNhbGx5IHByb2R1Y2VzIGxhcmdlciBlcnJvcnMgd2hlbiBuZXcgaW5mb3JtYXRpb24gYmVjb21lcyBhdmFpbGFibGUuDQoNCjMuIEVkZ2UgZWZmZWN0cy4NCg0KQW5vdGhlciBjb25zZXF1ZW5jZSBvZiBvdmVyZml0dGluZywgaXMgdGhhdCB0aGUgcmVzdWx0aW5nIGZ1bmN0aW9ucyB0ZW5kIHRvIGRpc3BsYXkgZXh0cmVtZSBiZWhhdmlvciB3aGVuIHRha2VuIG91dHNpZGUgb2YgdGhlaXIgZXN0aW1hdGlvbiByYW5nZSwgd2hlcmUgdGhlIGxhcmdlc3QgcG9seW5vbWlhbCB0ZXJtcyB0ZW5kIHRvIGRvbWluYXRlLiANCg0KVGhlIHBsb3QgYmVsb3cgaXMgdGhlIHNhbWUgaGlnaCBkZWdyZWUgcG9seW5vbWlhbCBlc3RpbWF0ZWQgYWJvdmUsIGp1c3QgcGxvdHRlZCBpbiBhIHNsaWdodGx5IGxhcmdlciByYW5nZSBvZiBwbHVzL21pbnVzIG9uZSB1bml0Og0KYGBge3J9DQpwb2x5LmZ1biA8LSBwcmVkaWN0KG1vZC5vZjIsIGRhdGEuZnJhbWUoeCA9IHNlcSgwLCAxMSwgMC4xKSkpDQpwICsgDQogIGdlb21fbGluZShkYXRhID0gZGF0YS5mcmFtZSh4ID0gc2VxKDAsIDExLCAwLjEpLCB5ID0gcG9seS5mdW4pLCBhZXMoeCA9IHgsIHkgPSB5KSwNCiAgICAgICAgICAgICAgICBjb2xvciA9ICJibHVlIiwgc2l6ZSA9IDEpICsgDQogIGdlb21fcG9pbnQoZGF0YSA9IGRmLm9mMiwgYWVzKHggPSB4LCB5ID0geSksIHNoYXBlID0gMCwgY29sb3IgPSAicmVkIikgKw0KICBnZW9tX3NlZ21lbnQoZGF0YSA9IGRmLm9mMiwgYWVzKHhlbmQgPSB4LCB5ZW5kID0gcHJlZDIpKSArIA0KICBnZW9tX3BvaW50KHNpemUgPSAzKQ0KYGBgDQoNCiMjIE1vZGVscyB3aXRoIHNwYXRpYWxseSB2YXJ5aW5nIGNvZWZmaWNpZW50cw0KDQpBbm90aGVyIHdheSB0byBnZW5lcmF0ZSBmbGV4aWJsZSBmdW5jdGlvbmFsIGZvcm1zIGlzIGJ5IG1lYW5zIG9mIG1vZGVscyB3aXRoIHNwYXRpYWxseSB2YXJ5aW5nIGNvZWZmaWNpZW50cy4gVHdvIGFwcHJvYWNoZXMgYXJlIHJldmlld2VkIGhlcmUuDQoNCiMjIyBFeHBhbnNpb24gbWV0aG9kDQoNClRoZSBleHBhbnNpb24gbWV0aG9kIChbQ2FzZXR0aSwgMTk3Ml0oaHR0cDovL29ubGluZWxpYnJhcnkud2lsZXkuY29tL2RvaS8xMC4xMTExL2ouMTUzOC00NjMyLjE5NzIudGIwMDQ1OC54L2Z1bGwpKSBpcyBhbiBhcHByb2FjaCB0byBnZW5lcmF0ZSBtb2RlbHMgd2l0aCBjb250ZXh0dWFsIGVmZmVjdHMuIEl0IGZvbGxvd3MgYSBwaGlsb3NvcGh5IG9mIHNwZWNpZnlpbmcgZmlyc3QgYSBzdWJzdGFudGl2ZSBtb2RlbCB3aXRoIHZhcmlhYmxlcyBvZiBpbnRlcmVzdCwgYW5kIHRoZW4gYW4gZXhwYW5kZWQgbW9kZWwgd2l0aCBjb250ZXh0dWFsIHZhcmlhYmxlcy4gSW4gZ2VvZ3JhcGhpY2FsIGFuYWx5c2lzLCB0eXBpY2FsbHkgdGhlIGNvbnRleHR1YWwgdmFyaWFibGVzIGFyZSB0cmVuZCBzdXJmYWNlcyBlc3RpbWF0ZWQgdXNpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBvYnNlcnZhdGlvbnMuDQoNClRvIGlsbHVzdHJhdGUgdGhpcywgc3VwcG9zZSB0aGF0IHRoZXJlIGlzIHRoZSBmb2xsb3dpbmcgaW5pdGlhbCBtb2RlbCBvZiBwcm9wb3J0aW9uIG9mIGRvbm9ycyBpbiBhIHBvcHVsYXRpb24sIHdpdGggdHdvIHZhcmlhYmxlcyBvZiBzdWJzdGFudGl2ZSBpbnRlcmVzdCAoc2F5LCBpbmNvbWUgYW5kIGVkdWNhdGlvbik6DQokJA0KZF9pID0gXGJldGFfaSh4X2kseV9pKSArIFxiZXRhXzEoeF9pLHlfaSlJX2kgKyBcYmV0YV8zKHhfaSx5X2kpRWRfaSArIFxlcHNpbG9uX2kNCiQkDQoNCk5vdGUgaG93IHRoZSBjb2VmZmljaWVudHMgYXJlIG5vdyBhIGZ1bmN0aW9uIG9mIHRoZSBjb29yZGluYXRlcyBhdCAkaSQuIFVubGlrZSBwcmV2aW91cyBtb2RlbHMgdGhhdCBoYWQgX2dsb2JhbF8gY29lZmZpY2llbnRzLCB0aGUgY29lZmZpY2llbnRzIGluIHRoaXMgbW9kZWwgYXJlIGFsbG93ZWQgdG8gYWRhcHQgYnkgbG9jYXRpb24uDQoNClVuZm9ydHVuYXRlbHksIGl0IGlzIG5vdCBwb3NzaWJsZSB0byBlc3RpbWF0ZSBvbmUgY29lZmZpY2llbnQgcGVyIGxvY2F0aW9uLiBJbiB0aGlzIGNhc2UsIHRoZXJlIGFyZSAkblx0aW1lcyBrJCBjb2VmZmljaWVudHMsIHdoaWNoIGV4Y2VlZHMgdGhlIHNpemUgb2YgdGhlIHNhbXBsZSAoJG4kKS4gSXQgaXMgbm90IHBvc3NpYmxlIHRvIHJldHJpZXZlIG1vcmUgaW5mb3JtYXRpb24gZnJvbSB0aGUgc2FtcGxlIHRoYW4gJG4kIHBhcmFtZXRlcnMgKHRoaXMgaXMgY2FsbGVkIHRoZSBpbmNpZGVudGFsIHBhcmFtZXRlciBwcm9ibGVtLikNCg0KQSBwb3NzaWJsZSBzb2x1dGlvbiBpcyB0byBzcGVjaWZ5IGEgZnVuY3Rpb24gZm9yIHRoZSBjb2VmZmljaWVudHMsIGZvciBpbnN0YW5jZSwgYnkgc3BlY2lmeWluZyBhIHRyZW5kIHN1cmZhY2UgZm9yIHRoZW06DQokJA0KXGJlZ2lue2FycmF5fXtsfQ0KXGJldGFfMCh4X2ksIHlfaSkgPSBcYmV0YV97MDF9ICtcYmV0YV97MDJ9eF9pICsgXGJldGFfezAzfXlfaVxcDQpcYmV0YV8xKHhfaSwgeV9pKSA9IFxiZXRhX3sxMX0gK1xiZXRhX3sxMn14X2kgKyBcYmV0YV97MTN9eV9pXFwNClxiZXRhXzIoeF9pLCB5X2kpID0gXGJldGFfezIxfSArXGJldGFfezIyfXhfaSArIFxiZXRhX3syM315X2kNClxlbmR7YXJyYXl9DQokJA0KQnkgc3BlY2lmeWluZyB0aGUgY29lZmZpY2llbnRzIGFzIGEgZnVuY3Rpb24gb2YgdGhlIGNvb3JkaW5hdGVzLCB3ZSBhbGxvdyB0aGVtIHRvIHZhcnkgYnkgbG9jYXRpb24uDQoNCk5leHQsIGlmIHdlIHN1YnN0aXR1dGUgdGhlc2UgY29lZmZpY2llbnRzIGluIHRoZSBpbnRpYWwgbW9kZWwsIHdlIGFycml2ZSBhdCBhIGZpbmFsIGV4cGFuZGVkIG1vZGVsOg0KJCQNCmRfaSA9IFxiZXRhX3swMX0gK1xiZXRhX3swMn14X2kgKyBcYmV0YV97MDN9eV9pICsgXGJldGFfezExfUlfaSArXGJldGFfezEyfXhfaUlfaSArIFxiZXRhX3sxM315X2lJX2kgKyBcYmV0YV97MjF9RWRfaSArXGJldGFfezIyfXhfaUVkX2kgKyBcYmV0YV97MjN9eV9pRWRfaSArIFxlcHNpbG9uX2kNCiQkDQoNClRoaXMgbW9kZWwgaGFzIG5vdyBuaW5lIGNvZWZmaWNpZW50cywgaW5zdGVhZCBvZiAkblx0aW1lcyAzJCwgYW5kIGNhbiBiZSBlc3RpbWF0ZWQgYXMgdXN1YWwuDQoNCkl0IGlzIGltcG9ydGFudCB0byBub3RlIHRoYXQgc2luY2UgbW9kZWxzIGdlbmVyYXRlZCBiYXNlZCBvbiB0aGUgZXhwYW5zaW9uIG1ldGhvZCBhcmUgYmFzZWQgb24gdGhlIHVzZSBvZiB0cmVuZCBzdXJmYWNlcywgc2ltaWxhciBjYXZlYXRzIGFwcGx5IHdpdGggcmVzcGVjdCB0byBtdWx0aWNvbGxpbmVhcml0eSBhbmQgb3ZlcmZpdHRpbmcuDQoNCiMjIyBHZW9ncmFwaGljYWxseSB3ZWlnaHRlZCByZWdyZXNzaW9uIChHV1IpDQoNCkEgZGlmZmVyZW50IHN0cmF0ZWd5IHRvIGVzdGltYXRlIG1vZGVscyB3aXRoIHNwYXRpYWxseS12YXJ5aW5nIGNvZWZmaWNpZW50cyBpcyBhIHNlbWktcGFyYW1ldHJpYyBhcHByb2FjaCwgY2FsbGVkIGdlb2dyYXBoaWNhbGx5IHdlaWdodGVkIHJlZ3Jlc3Npb24gKHNlZSBbQnJ1bnNkb24gZXQgYWwuLCAxOTk2XShodHRwOi8vb25saW5lbGlicmFyeS53aWxleS5jb20vZG9pLzEwLjExMTEvai4xNTM4LTQ2MzIuMTk5Ni50YjAwOTM2LngvYWJzdHJhY3QpKS4NCg0KSW5zdGVhZCBvZiBzZWxlY3RpbmcgYSBmdW5jdGlvbmFsIGZvcm0gZm9yIHRoZSBjb2VmZmljaWVudHMgYXMgdGhlIGV4cGFuc2lvbiBtZXRob2QgZG9lcywgdGhlIGZ1bmN0aW9ucyBhcmUgbGVmdCB1bnNwZWNpZmllZC4gVGhlIHNwYXRpYWwgdmFyaWF0aW9uIG9mIHRoZSBjb2VmZmljaWVudHMgcmVzdWx0cyBmcm9tIGFuIGVzdGltYXRpb24gc3RyYXRlZ3kgdGhhdCB0YWtlcyBzdWJzYW1wbGVzIG9mIHRoZSBkYXRhIGluIGEgc3lzdGVtYXRpYyB3YXkuDQoNCklmIHlvdSByZWNhbGwga2VybmVsIGRlbnNpdHkgYW5hbHlzaXMsIGEga2VybmVsIHdhcyBhIHdheSBvZiB3ZWlnaHRpbmcgb2JzZXJ2YXRpb25zIGJhc2VkIG9uIHRoZWlyIGRpc3RhbmNlIGZyb20gYSBmb2NhbCBwb2ludC4NCg0KR2VvZ3JhcGhpY2FsbHkgd2VpZ2h0ZWQgcmVncmVzc2lvbiBhcHBsaWVzIGEgc2ltaWxhciBjb25jZXB0LCB3aXRoIGEgbW92aW5nIHdpbmRvdyB0aGF0IHZpc2l0cyBhIGZvY2FsIHBvaW50IGFuZCBlc3RpbWF0ZXMgYSB3ZWlnaHRlZCBsZWFzdCBzcXVhcmVzIG1vZGVsIGF0IHRoYXQgbG9jYXRpb24uIFRoZSByZXN1bHRzIG9mIHRoZSByZWdyZXNzaW9uIGFyZSBjb252ZW50aW9uYWxseSBhcHBsaWVkIHRvIHRoZSBmb2NhbCBwb2ludCwgaW4gc3VjaCBhIHdheSB0aGF0IG5vdCBvbmx5IHRoZSBjb2VmZmljaWVudHMgYXJlIGxvY2FsaXplZCwgYnV0IGFsc28gZXZlcnkgb3RoZXIgcmVncmVzc2lvbiBkaWFnbm9zdGljIChlLmcuLCB0aGUgY29lZmZpY2llbnQgb2YgZGV0ZXJtaW5hdGlvbiwgdGhlIHN0YW5kYXJkIGRldmlhdGlvbiwgZXRjLikNCg0KQSBrZXkgYXNwZWN0IG9mIGltcGxlbWVudGluZyB0aGlzIG1vZGVsIGlzIHRoZSBzZWxlY3Rpb24gb2YgdGhlIGtlcm5lbCBiYW5kd2lkdGgsIHRoYXQgaXMsIHRoZSBzaXplIG9mIHRoZSB3aW5kb3cuIElmIHRoZSB3aW5kb3cgaXMgdG9vIGxhcmdlLCB0aGUgbG9jYWwgbW9kZWxzIHRlbmQgdG93YXJkcyB0aGUgZ2xvYmFsIG1vZGVsIChlc3RpbWF0ZWQgdXNpbmcgdGhlIHdob2xlIHNhbXBsZSkuIElmIHRoZSB3aW5kb3cgaXMgdG9vIHNtYWxsLCB0aGUgbW9kZWwgdGVuZHMgdG8gb3ZlcmZpdCwgc2luY2UgaW4gdGhlIGxpbWl0IGVhY2ggd2luZG93IHdpbGwgY29udGFpbiBvbmx5IG9uZSwgb3IgYSB2ZXJ5IHNtYWxsIG51bWJlciBvZiBvYnNlcnZhdGlvbnMuDQoNClRoZSBrZXJuZWwgYmFuZHdpZHRoIGNhbiBiZSBzZWxlY3RlZCBpZiB3ZSBkZWZpbmUgc29tZSBsb3NzIGZ1bmN0aW9uIHRvIG1pbmltaXplLiBBIGNvbnZlbnRpb25hbCBhcHByb2FjaCAoYnV0IG5vdCB0aGUgb25seSBvbmUpLCBpcyB0byBtaW5pbWl6ZSBhIGNyb3NzLXZhbGlkYXRpb24gc2NvcmUgb2YgdGhlIGZvbGxvd2luZyBmb3JtOg0KJCQNCkNWIChcZGVsdGEpID0gXHN1bV97aT0xfV5ue1xiaWcoeV9pIC0gXGhhdHt5fV97XG5lcSBpfShcZGVsdGEpXGJpZyleMn0NCiQkDQpJbiB0aGlzIG5vdGF0aW9uLCAkXGRlbHRhJCBpcyB0aGUgYmFuZHdpZHRoLCBhbmQgJFxoYXR7eX1fe1xuZXEgaX0oXGRlbHRhKSQgaXMgdGhlIHZhbHVlIG9mICR5JCBwcmVkaWN0ZWQgYnkgYSBtb2RlbCB3aXRoIGEgYmFuZHdpZHRoIG9mICRcZGVsdGEkIF9hZnRlciBleGNsdWRpbmcgdGhlIG9ic2VydmF0aW9uIGF0ICRpJF8uIFRoaXMgaXMgY2FsbGVkIGEgX2xlYXZlLW9uZS1vdXRfIGNyb3NzLXZhbGlkYXRpb24gcHJvY2VkdXJlLCB1c2VkIHRvIHByZXZlbnQgdGhlIGVzdGltYXRpb24gZnJvbSBzaHJpbmtpbmcgdGhlIGJhbmR3aWR0aCB0byB6ZXJvLg0KDQpHV1IgaXMgaW1wbGVtZW50ZWQgaW4gdGhlIHBhY2thZ2UgYHNwZ3dyYC4gVG8gZXN0aW1hdGUgbW9kZWxzIHVzaW5nIHRoaXMgYXBwcm9hY2gsIHRoZSBmdW5jdGlvbiBgc2VsLkdXUmAsIHdoaWNoIHRha2VzIGFzIGlucHV0cyBhIGZvcm11bGEgc3BlY2lmeWluZyB0aGUgZGVwZW5kZW50IGFuZCBpbmRlcGVuZGVudCB2YXJpYWJsZXMsIGEgYFNwYXRpYWxQb2x5Z29uc0RhdGFGcmFtZWAgKG9yIGEgYFNwYXRpYWxQb2ludHNEYXRhRnJhbWVgKSwgYW5kIHRoZSBrZXJuZWwgZnVuY3Rpb24gKGluIHRoZSBleGFtcGxlIGJlbG93IGEgR2F1c3NpYW4ga2VybmVsKToNCmBgYHtyfQ0KZGVsdGEgPC0gZ3dyLnNlbChmb3JtdWxhID0geiB+IHggKyB5LCBkYXRhID0gSGFtaWx0b25fVEFaLCBnd2VpZ2h0ID0gZ3dyLkdhdXNzKQ0KYGBgDQoNClRoZSBmdW5jdGlvbiBgZ3dyYCBlc3RpbWF0ZXMgdGhlIHN1aXRlIG9mIGxvY2FsIG1vZGVscyBnaXZlbiBhIGJhbmR3aWR0aDoNCmBgYHtyfQ0KbW9kZWwuZ3dyIDwtIGd3cihmb3JtdWxhID0geiB+IHggKyB5LCBiYW5kd2lkdGggPSBkZWx0YSwgZGF0YSA9IEhhbWlsdG9uX1RBWiwgZ3dlaWdodCA9IGd3ci5HYXVzcykNCm1vZGVsLmd3cg0KYGBgDQoNClRoZSByZXN1bHRzIGFyZSBnaXZlbiBmb3IgZWFjaCBsb2NhdGlvbiB3aGVyZSBhIGxvY2FsIHJlZ3Jlc3Npb24gd2FzIGVzdGltYXRlZC4gTGV0cyBhcHBlbmQgdG8gb3VyIHRpZHkgZGF0YWZyYW1lIGZvciBwbG90dGluZzoNCmBgYHtyfQ0KSGFtaWx0b25fVEFaLnQgPC0gbGVmdF9qb2luKEhhbWlsdG9uX1RBWi50LCANCiAgICAgICAgICAgICAgICAgIGRhdGEuZnJhbWUoR1RBMDYgPSBIYW1pbHRvbl9UQVokR1RBMDYsIG1vZGVsLmd3ciRTREZAZGF0YSkpDQpIYW1pbHRvbl9UQVoudCA8LSByZW5hbWUoSGFtaWx0b25fVEFaLnQsIGJldGEwID0gWC5JbnRlcmNlcHQuLCBiZXRhMSA9IHgsIGJldGEyID0geSkNCmBgYA0KDQpUaGUgcmVzdWx0cyBjYW4gYmUgbWFwcGVkIGFzIHNob3duIGJlbG93ICh0cnkgbWFwcGluZyBgYmV0YTFgLCBgYmV0YTJgLCBgbG9jYWxSMmAsIG9yIHRoZSByZXNpZHVhbHMgYGd3ci5lYCk6DQpgYGB7cn0NCmdncGxvdChkYXRhID0gSGFtaWx0b25fVEFaLnQsIGFlcyh4ID0gbG9uZywgeSA9IGxhdCwgZ3JvdXAgPSBncm91cCwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmaWxsID0gYmV0YTApKSArIA0KICBnZW9tX3BvbHlnb24oY29sb3IgPSAid2hpdGUiKSArDQogIHNjYWxlX2ZpbGxfZGlzdGlsbGVyKHBhbGV0dGUgPSAiWWxPclJkIiwgdHJhbnMgPSAicmV2ZXJzZSIpICsNCiAgY29vcmRfZXF1YWwoKQ0KYGBgDQoNCllvdSBjYW4gdmVyaWZ5IHRoYXQgdGhlIHJlc2lkdWFscyBhcmUgbm90IHNwYXRpYWxseSBhdXRvY29ycmVsYXRlZDoNCmBgYHtyfQ0KbW9yYW4udGVzdChtb2RlbC5nd3IkU0RGJGd3ci5lLCBIYW1pbHRvbl9UQVoudykNCmBgYA0KDQpTb21lIGNhdmVhdHMgd2l0aCByZXNwZWN0IHRvIEdXUi4gDQoNClNpbmNlIGVzdGltYXRpb24gcmVxdWlyZXMgdGhlIHNlbGVjdGlvbiBvZiBhIGtlcm5lbCBiYW5kd2lkdGgsIGFuZCBhIGtlcm5lbCBiYW5kd2lkdGggcmVxdWlyZXMgdGhlIGVzdGltYXRpb24gb2YgbWFueSB0aW1lcyBsZWF2ZS1vbmUtb3V0IHJlZ3Jlc3Npb25zLCBHV1IgY2FuIGJlIGNvbXB1dGF0aW9uYWxseSBxdWl0ZSBkZW1hbmRpbmcsIGVzcGVjaWFsbHkgZm9yIGxhcmdlIGRhdGFzZXRzLg0KDQpHV1IgaGFzIGJlY29tZSBhIHZlcnkgcG9wdWxhciBtZXRob2QsIGhvd2V2ZXIsIHRoZXJlIGlzIGNvbmZsaWN0aW5nIGV2aWRlbmNlIHJlZ2FyZGluZyBpdHMgYWJpbGl0eSB0byByZXRyaWV2ZSBhIGtub3duIHNwYXRpYWwgcHJvY2VzcywgYW5kIGludGVycHJldGF0aW9uIG9mIHRoZSBzcGF0aWFsbHktdmFyeWluZyBjb2VmZmljaWVudHMgbXVzdCBiZSBjb25kdWN0ZWQgd2l0aCBhIGdyYWluIG9mIHNhbHQsIGFsdGhvdWdoIHRoaXMgc2VlbXMgdG8gYmUgbGVzcyBvZiBhIGNvbmNlcm4gd2l0aCBsYXJnZXIgc2FtcGxlcyAtIGJ1dCBhdCB0aGUgbW9tZW50IGl0IGlzIG5vdCBrbm93biBob3cgbGFyZ2UgYSBzYW1wbGUgaXMgc2FmZSAoYW5kIGxhcmdlciBzYW1wbGVzIGFsc28gYmVjb21lIGNvbXB1dGF0aW9uYWxseSBtb3JlIGRlbWFuZGluZykuIEFzIHdlbGwsIHRoZSBlc3RpbWF0aW9uIG1ldGhvZCBpcyBrbm93biB0byBiZSBzZW5zaXRpdmUgdG8gdW51c3VhbCBvYnNlcnZhdGlvbnMuIEF0IHRoZSBtb21lbnQsIEkgcmVjb21tZW5kIHRoYXQgR1dSIGJlIHVzZWQgZm9yIHByZWRpY3Rpb24gb25seSwgYW5kIGluIHRoaXMgcmVzcGVjdCBpdCBzZWVtcyB0byBwZXJmb3JtIGFzIHdlbGwsIG9yIGV2ZW4gYmV0dGVyIHRoYW4gYWx0ZXJuYXRpdmVzIGFwcHJvYWNoZXMuDQoNCiMgU3BhdGlhbCBFcnJvciBNb2RlbCAoU0VNKQ0KDQpBIG1vZGVsIHRoYXQgY2FuIGJlIHVzZWQgdG8gdGFrZSBkaXJlY3QgcmVtZWRpYWwgYWN0aW9uIHdpdGggcmVzcGVjdCB0byByZXNpZHVhbCBzcGF0aWFsIGF1dG9jb3JyZWxhdGlvbiBpcyB0aGUgc3BhdGlhbCBlcnJvciBtb2RlbC4NCg0KVGhpcyBtb2RlbCBpcyBzcGVjaWZpZWQgYXMgZm9sbG93czoNCiQkDQp5X2kgPSBcYmV0YV8wICsgXHN1bV97aj0xfV5re1xiZXRhX2t4X3tpan19ICsgXGVwc2lsb25faQ0KJCQNCg0KSG93ZXZlciwgaXQgaXMgbm8gbG9uZ2VyIGFzc3VtZWQgdGhhdCB0aGUgcmVzaWR1YWxzICRcZXBzaWxvbiQgYXJlIGluZGVwZW5kZW50LCBidXQgaW5zdGVhZCBkaXNwbGF5IG1hcCBwYXR0ZXJuLCBpbiB0aGUgc2hhcGUgb2YgYSBtb3ZpbmcgYXZlcmFnZToNCiQkDQpcZXBzaWxvbl9pID0gXGxhbWJkYVxzdW1fe2k9MX1ebnt3X3tpan1ee3N0fVxlcHNpbG9uX2l9ICsgXG11X2kNCiQkDQoNCkEgc2Vjb25kIHNldCBvZiByZXNpZHVhbHMgJFxtdSQgYXJlIGFzc3VtZWQgdG8gYmUgaW5kZXBlbmRlbnQuDQoNCkl0IGlzIHBvc3NpYmxlIHRvIHNob3cgdGhhdCB0aGlzIG1vZGVsIGlzIG5vIGxvbmdlciBsaW5lYXIgaW4gdGhlIGNvZWZmaWNpZW50cyAoYnV0IHRoaXMgd291bGQgcmVxdWlyZSBhIGxpdHRsZSBiaXQgb2YgbWF0cml4IGFsZ2VicmEpLiBGb3IgdGhpcyByZWFzb24sIG9yZGluYXJ5IGxlYXN0IHNxdWFyZXMgaXMgbm8gbG9uZ2VyIGFuIGFwcHJvcHJpYXRlIGVzdGltYXRpb24gYWxnb3JpdGhtLCBhbmQgbW9kZWxzIG9mIHRoaXMga2luZCBhcmUgaW5zdGVhZCBlc3RpbWF0ZWQgYmFzZWQgb24gbWF4aW11bSBsaWtlbGlob29kLg0KDQpTcGF0aWFsIGVycm9yIG1vZGVscyBhcmUgaW1wbGVtZW50ZWQgaW4gdGhlIHBhY2thZ2UgYHNwZGVwYC4NCg0KQXMgYSByZW1lZGlhbCBtb2RlbCwgaXQgY2FuIGFjY291bnQgZm9yIGEgbW9kZWwgd2l0aCBhIG1pc3NwZWNpZmllZCBmdW5jdGlvbmFsIGZvcm0uIFdlIGtub3cgdGhhdCB0aGUgdW5kZXJseWluZyBwcm9jZXNzIGlzIG5vdCBsaW5lYXIsIGJ1dCB3ZSBzcGVjaWZ5IGEgbGluZWFyIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIHRoZSBjb3ZhcmlhdGVzIGluIHRoZSBmb3JtIG9mICR6ID0gXGJldGFfMCArIFxiZXRhXzF4ICsgXGJldGFfMnkkOg0KYGBge3J9DQptb2RlbC5zZW0xIDwtIGVycm9yc2FybG0oZm9ybXVsYSA9IHogfiB4ICsgeSwgDQogICAgICAgICAgICAgICAgICAgICAgICBkYXRhID0gSGFtaWx0b25fVEFaQGRhdGEsIA0KICAgICAgICAgICAgICAgICAgICAgICAgbGlzdHcgPSBIYW1pbHRvbl9UQVoudykNCnN1bW1hcnkobW9kZWwuc2VtMSkNCmBgYA0KDQpUaGUgY29lZmZpY2llbnQgJFxsYW1iZGEkIGlzIHBvc2l0aXZlIChpbmRpY2F0aXZlIG9mIHBvc2l0aXZlIGF1dG9jb3JyZWxhdGlvbikgYW5kIGhpZ2gsIHNpbmNlIGFib3V0IDUwJSBvZiB0aGUgbW92aW5nIGF2ZXJhZ2Ugb2YgdGhlIHJlc2lkdWFscyAkXGVwc2lsb24kIGluIHRoZSBuZWlnaGJvcmhvb2Qgb2YgJGkkIGNvbnRyaWJ1dGUgdG8gdGhlIHZhbHVlIG9mICRcZXBzaWxvbl9pJC4gDQoNCllvdSBjYW4gdmVyaWZ5IHRoYXQgdGhlIHJlc2lkdWFscyBhcmUgc3BhdGlhbGx5IHVuY29ycmVsYXRlZCAobm90ZSB0aGF0IHRoZSBhbHRlcm5hdGl2ZSBpcyAibGVzcyIgYmVjYXVzZSBvZiB0aGUgbmVnYXRpdmUgc2lnbiBvZiBNb3JhbidzIEkgY29lZmZpY2llbnQpOg0KYGBge3J9DQptb3Jhbi50ZXN0KG1vZGVsLnNlbTEkcmVzaWR1YWxzLCBIYW1pbHRvbl9UQVoudywgYWx0ZXJuYXRpdmUgPSAibGVzcyIpDQpgYGANCg0KTm93IGNvbnNpZGVyIHRoZSBjYXNlIG9mIGEgbWlzc2luZyBjb3ZhcmlhdGU6DQpgYGB7cn0NCm1vZGVsLnNlbTIgPC0gZXJyb3JzYXJsbShmb3JtdWxhID0gbG9nKHopIH4geCwgDQogICAgICAgICAgICAgICAgICAgICAgICBkYXRhID0gSGFtaWx0b25fVEFaQGRhdGEsIA0KICAgICAgICAgICAgICAgICAgICAgICAgbGlzdHcgPSBIYW1pbHRvbl9UQVoudykNCnN1bW1hcnkobW9kZWwuc2VtMikNCmBgYA0KDQpJbiB0aGlzIGNhc2UsIHRoZSByZXNpZHVhbCBwYXR0ZXJuIGlzIHBhcnRpY3VsYXJseSBzdHJvbmcsIHdpdGggbW9yZSB0aGFuIDkwJSBvZiB0aGUgbW92aW5nIGF2ZXJhZ2UgY29udHJpYnV0aW5nIHRvIA0KDQpBbGFzLCBpbiB0aGlzIGNhc2UsIHRoZSByZW1lZGlhbCBhY3Rpb24gZmFsbHMgc2hvcnQgb2YgY2xlYW5pbmcgdGhlIHJlc2lkdWFscywgYW5kIHdlIGNhbiBzZWUgdGhhdCB0aGV5IHN0aWxsIHJlbWFpbiBzcGF0aWFsbHkgY29ycmVsYXRlZDoNCmBgYHtyfQ0KbW9yYW4udGVzdChtb2RlbC5zZW0yJHJlc2lkdWFscywgSGFtaWx0b25fVEFaLncsIGFsdGVybmF0aXZlID0gImxlc3MiKQ0KYGBgDQoNClRoaXMgd291bGQgc3VnZ2VzdCB0aGUgbmVlZCBmb3IgYWx0ZXJuYXRpdmUgYWN0aW9uIChzdWNoIGFzIHRoZSBzZWFyY2ggZm9yIGFkZGl0aW9uYWwgY292YXJpYXRlcykuDQoNCklkZWFsbHksIGEgbW9kZWwgc2hvdWxkIGJlIHdlbGwtc3BlY2lmaWVkLCBhbmQgcmVtZWRpYWwgYWN0aW9uIHNob3VsZCBiZSB1bmRlcnRha2VuIG9ubHkgd2hlbiBvdGhlciBhbHRlcm5hdGl2ZXMgaGF2ZSBiZWVuIGV4aGF1c3RlZC4gDQoNClRoaXMgY29uY2x1ZGVzIFByYWN0aWNlIDE1Lg==